LeetCode链表简单题
2019-07-24 09:10:13来源:博客园 阅读 ()
一、21合并两个有序链表
代码如下:
class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: # 首先对特殊情况进行处理,l1 l2 为空的时候 if not (l1 and l2) : # 这个表达式的意思只要l1 l2 不全为真就符合条件 return l1 or l2 elif l1.val > l2.val: # 判断哪一个值比较小,然后保留哪一项 l2.next = self.mergeTwoLists(l2.next,l1) # 递归思想的精髓 return l2 # 返回小的这一项 else : l1.next = self.mergeTwoLists(l1.next,l2) return l1 # 注意:l1 l2 表示的不是整个链表,而只是每一个结点 # 这个是别人给的题解,大佬写的很好。 class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: if l1 and l2: # 判断l1 是否为空 if l1.val > l2.val : l1,l2 = l2,l1 # 始终让l1 为小值 l1.next = self.mergeTwoLists(l1.next,l2) # 递归的精髓 return l1 or l2
二、83删除链表重复的元素
class Solution: def deleteDuplicates(self, head: ListNode) -> ListNode: if not head :return head # 首先判断链表是否为空,若为空直接返回 head1 = head l = [] # 定义一个空的列表 用来存放已经遍历过的链表结点 l.append(head.val) # 将遍历过的链表结点添加进入列表中 while head and head.next: # 当前结点和下一个结点都为真继续 if head.next.val in l : # 若下一节点的值已经在列表中 head.next = head.next.next # 进行删除操作,跳过下一节点,直接指向下下结点 else: l.append(head.next.val) # 将结点添加进入列表 head = head.next # 进行遍历 return head1 # 返回删除重复元素后的链表
三、141环形链表
# 解题思路;利用快慢指针,一个指针快,另一个慢,若链表有环,则总有相遇的时候 class Solution(object): def hasCycle(self, head): """ :type head: ListNode :rtype: bool """ if not head or not head.next : # 若链表中没有元素,或者只有一个元素,则不可能成环 return False fast = head slow = head while fast: if fast.next == None: # 若快指针可以走到头,则肯定没有环 return False else : fast = fast.next.next # 快指针每次走两步 slow = slow.next # 慢指针走一步 if slow == fast: # 当快慢指针相遇 return True return False # 当快指针为None时退出
四、160相交链表
class Solution(object): def getIntersectionNode(self, headA, headB): """ :type head1, head1: ListNode :rtype: ListNode """ if not headA or not headB: # 若两个链表中其中一个链表为空则不可能相交 return None length1 = 0 # 用来接收headA链表的长度 length2 = 0 h1 = headA h2 = headB while h1: # 遍历链表算出两个链表的长度 length1 += 1 h1 = h1.next while h2: length2 += 1 h2 = h2.next if length1 > length2: # 让比较长的链表先走 for i in range(length1 - length2): headA = headA.next elif length1 < length2: for i in range(length2 - length1): headB = headB.next while headA: # 现在两个指针处于同一位置 if headA == headB: # 判断是否为同一节点 return headA headA = headA.next headB = headB.next return None
五、203移除链表元素
class Solution(object): def removeElements(self, head, val): """ :type head: ListNode :type val: int :rtype: ListNode """ if not head:return head # 判断是否为空链表 head1 = head # 用head1返回新的链表 while head: # 找到第一个不需要删除的链表 if head.val == val: # 需要删除时,将head1等于head的下一节点 head1 = head.next head = head.next else: break while head and head.next: # 进行链表的遍历,进行删除所给的元素 if head.next.val == val: head.next = head.next.next else : head = head.next return head1 # 返回新的链表
六、234回文链表
# 用快慢指针的方法找到链表的中间节点,然后将后半段链表进行反转,在判断 class Solution: def isPalindrome(self, head: ListNode) -> bool: if not head or not head.next : # 若链表为空或为一个元素,则链表为回文链表 return True fast = head slow = head # 快慢指针 快指针走两步,慢指针走一步 while fast and fast.next: fast = fast.next.next slow = slow.next mid = slow # 此时slow为中点指针 pre = None # 将后半段链表表反转 while slow: slow.next,pre,slow = pre,slow,slow.next # 不可以分开写成三个语句,Python特有,在C语言中这样写是错误的 # 他们这三个语句的执行是相同,没有先后之分。 # 此时后半段列表的头指针为pre while head != mid: if head.val != pre.val: return False pre = pre.next head = head.next return True
原文链接:https://www.cnblogs.com/cong12586/p/11111214.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- python爬虫学习之用Python抢火车票的简单小程序 2019-08-13
- 用python写一个简单的文件上传 2019-07-24
- concurrent.futures模块简单介绍(线程池,进程池) 2019-07-24
- ORM 2019-07-24
- celery 分布式异步任务框架(celery简单使用、celery多任务结 2019-07-24
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash