LeetCode链表简单题

2019-07-24 09:10:13来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

一、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入门教程完整版(懂中文就能学会)(600集)

下一篇:python学习-21 集合 2