博客

链表_总结(重点：环形链表)

  • Post author:
  • Post category:其他




链表



141. 环形链表!

判断是否有环


面试问的比较多的一道题


https://leetcode.cn/problems/linked-list-cycle/

给你一个链表的头节点 head ，判断链表中是否有环。


哈希表 链表 双指针

思路：利用快慢指针判断

我的思路：不对，这样不叫快慢指针，只是快指针在慢指针前面一步，但是前进的速度一样，这样永远追不上。 

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = head
        fast = head.next
        while fast.next != None:
            if slow != fast:
                fast = fast.next
                slow = slow.next
            else:
                return True
        return False



方法一：快慢指针


注

，边界条件：如果链表是否为空或只有一个元素，肯定不存在环。

需要判断slow != fast，所以不能把slow和fast都设为head，而是slow设为head，fast设为head.next。 

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return False
        # 快慢指针
        slow = head
        fast = head.next

        while fast and fast.next:
            if slow != fast:
                fast = fast.next.next
                slow = slow.next
            else:
                return True
        return False

答案形式： 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return False

        slow = head
        fast = head.next
        while slow != fast:
            if not fast or not fast.next:
                return False
            slow = slow.next
            fast = fast.next.next
        
        return True
  • 时间复杂度：O(N)，其中 N 是链表中的节点数。

    当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次。当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动 N 轮。
  • 空间复杂度：O(1)。我们只使用了两个指针的额外空间。



方法二：哈希表（更好理解）

使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程，直到我们遍历完整个链表即可。 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        # 哈希表
        record = set()
        cur = head
        while cur != None:
            if cur in record:  # 直接判断节点
                return True
            record.add(cur)
            cur = cur.next
        return False

  • 时间复杂度：O(N)，其中 N 是链表中的节点数。最坏情况下我们需要遍历每个节点一次。

  • 空间复杂度：O(N)，其中 N 是链表中的节点数。主要为哈希表的开销，最坏情况下我们需要将每个节点插入到哈希表中一次。



补充：142.环形链表II

返回入环节点

https://leetcode.cn/problems/linked-list-cycle-ii/

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。



方法一：快慢指针

前提：

快指针和慢指针都指向头节点

。!!! 计算快指针和慢指针走过的距离，任意时刻，

fast 指针走过的距离都为 slow 指针的 2 倍

。建立等式。得出结论：

从相遇点到入环点的距离加上 n-1 圈的环长，恰好等于从链表头部到入环点的距离

。

因此，当发现 slow 与 fast 相遇时，我们再额外使用一个指针 ptr。起始，它指向链表头部；随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇。（起始点指针和相遇点指针） 

# 代码随想录
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        # 快慢指针，起始点指针，相遇点指针
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                p = head   # 起始点
                q = slow   # 相遇点
                while p != q:
                    p = p.next
                    q = q.next
                return p
        return None



方法二：哈希表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        # 哈希表
        record = set()
        cur = head
        while cur:
            if cur in record:
                return cur
            record.add(cur)
            cur = cur.next
        return None



怎么计算环内有几个节点？



方法一：

若链表中存在环，则快指针与慢指针必定相遇于环中任一结点，因此

相遇时我们开始计数直到下次相遇

，慢指针所移动步数即为环中结点个数（设环中结点数为r，另设从第一次相遇开始到第二次相遇时慢指针移动S步，那么快指针移动步数为2S，且有2S=S+r，因此r=S）。

我的写法： 

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                slow = slow.next
                fast = fast.next.next
                n = 1 # 统计环内节点数
                while slow != fast:
                    slow = slow.next
                    fast = fast.next.next
                    n += 1 
                # print(n)
                return n
        return 0


我的思路：起始点指针和相遇点指针到达入口节点前走过的节点数 + 从入口节点处到相遇点处的节点数 = 环内的节点数。


但是代码这样写，当链表是一个环时，记录的节点数为0。 

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        # # 快慢指针，起始点指针，相遇点指针
        slow = head
        fast = head
        n = 0  # 统计环内节点数
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                p = head   # 起始点
                q = slow   # 相遇点
                while p != q:
                    p = p.next
                    q = q.next
                    n += 1
                while q != fast:
                    q = q.next
                    n += 1
                print(n)
                return p
        return None



21. 合并两个有序链表

https://leetcode.cn/problems/merge-two-sorted-lists/


递归 链表



方法一：递归（不太能理解）

https://leetcode.cn/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/ 

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        elif l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2



方法二：迭代（更好理解）

定义一个虚拟节点

https://leetcode.cn/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/ 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummyHead = ListNode(-1)
        cur = dummyHead
        while l1 and l2:
            if l1.val <= l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        # l1和l2中至少有一个不为None, 将链表末尾指向未合并完的链表
        cur.next = l1 if l1 else l2
        return dummyHead.next
  • 时间复杂度：O(n + m)，其中 n 和 m 分别为两个链表的长度。因为每次循环迭代中，l1 和 l2 只有一个元素会被放进合并链表中， 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的，因此总的时间复杂度为 O(n+m)。
  • 空间复杂度：O(1)。我们只需要常数的空间存放若干变量。



203. 移除链表元素

https://leetcode.cn/problems/remove-linked-list-elements/

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        dummyHead = ListNode(-1)
        cur = dummyHead
        dummyHead.next = head
        while cur.next != None:
            if cur.next.val == val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return dummyHead.next

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        dummyHead = ListNode(next = head)
        curNode = dummyHead
        while(curNode.next != None):
            if(curNode.next.val == val):
                curNode.next = curNode.next.next
            else:
                curNode = curNode.next
        return dummyHead.next



206. 反转链表

https://leetcode.cn/problems/reverse-linked-list/?envType=study-plan&id=shu-ju-jie-gou-ru-men

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        pre = None
        while cur != None:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        return pre



83. 删除排序链表中的重复元素

https://leetcode.cn/problems/remove-duplicates-from-sorted-list/

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

我的题解： 

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return head
        cur = head
        while cur.next != None:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head

答案： 

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return head

        cur = head
        while cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next

        return head



补充(算法学习计划_链表_双指针)：



876. 链表的中间结点

https://leetcode.cn/problems/middle-of-the-linked-list/

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。



方法一：快慢指针法

用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步，fast 一次走两步。那么当 fast 到达链表的末尾时，slow 必然位于中间。 

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

  • 时间复杂度：O(N)，其中 NN 是给定链表的结点数目。

  • 空间复杂度：O(1)，只需要常数空间存放 slow 和 fast 两个指针。



方法二：单指针法

可以对链表进行两次遍历。第一次遍历时，我们统计链表中的元素个数 N；第二次遍历时，我们遍历到第 N/2 个元素（链表的首节点为第 0 个元素）时，将该元素返回即可。 

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        n, cur = 0, head
        while cur:
            n += 1
            cur = cur.next
        k, cur = 0, head
        while k < n // 2:
            k += 1
            cur = cur.next
        return cur



24. 两两交换链表中的节点

https://leetcode.cn/problems/swap-nodes-in-pairs/

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。



方法一：直接交换

定义一个虚拟头节点 

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next: return head
        dummyNode = ListNode(next=head)
        cur = dummyNode
        while cur.next != None and cur.next.next != None:
            # 暂存，有点绕
            tmp = cur.next
            tmp1 = cur.next.next

            tmp.next = tmp1.next
            tmp1.next = tmp
            cur.next = tmp1


            # 循环，准备下一轮交换
            cur = cur.next.next
        return dummyNode.next



19. 删除链表的倒数第 N 个节点

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

给你一个链表，删除链表的倒数第 n 个节点，并且返回链表的头节点。

思路：定义一个

虚拟头节点

，利用

快慢指针

。首先，快慢指针都指向虚拟头节点，然后

快指针先走n步

，之后快慢指针同时向后移动，当快指针走到结尾时，

slow指针的下一个节点

为倒数第n个节点。 

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # 定义一个虚拟头节点
        dummyNode = ListNode()
        dummyNode.next = head

        slow = fast = dummyNode
        # 快指针先走n步
        for i in range(n):
            fast = fast.next
        
        while fast.next != None:
            slow = slow.next
            fast = fast.next

        # fast走到结尾后，slow的下一个节点为倒数第n个节点
        slow.next = slow.next.next
        return dummyNode.next

另一种写法：思路是一样的 

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummyNode = ListNode(next=head)
        slow = fast = dummyNode
        for i in range(n):
            fast = fast.next

        while fast.next != None:
            slow = slow.next
            fast = fast.next
        
        slow.next = slow.next.next
        return dummyNode.next

试了一下

return head

，在下面的情况下会报错。返回的是



[

1

]

[1]






[


1


]






输入：head = [1], n = 1

输出：[]



20221020 链表排序



148.排序链表&剑指 Offer II 077. 链表排序

  1. 排序链表 https://leetcode.cn/problems/sort-list/

给你链表的头结点

head

，请将其按

升序

排列并返回

排序后的链表

。


归并排序



147. 对链表进行插入排序

https://leetcode.cn/problems/insertion-sort-list/

给定单个链表的头 head ，使用

插入排序

对链表进行排序，并返回

排序后链表的头

。


插入排序

算法的步骤:

1.插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。

2.每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。

3.重复直到所有输入数据插入完为止。


版权声明：本文为Pythonistas29xs原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。