链表常见题目

常见题目

• 160 https://leetcode.cn/problems/intersection-of-two-linked-lists/
• 206 https://leetcode.cn/problems/reverse-linked-list
• 142 https://leetcode.cn/problems/linked-list-cycle-ii

160

https://fakelee.notion.site/160-Intersection-of-Two-Linked-Lists-847df477359e49409944a16301503f63?pvs=4

206

https://fakelee.notion.site/206-Reverse-Linked-List-5f35980f9a2e413cb9a7800a4da8aef3

142

思路

• 判断是否存在 cycle，fast/slow 指针相遇
• slow 和 slow2(head)一起移动，找到 cycle 起点

2slow = fast
2(P + C - X) = P + C + C - X
P = X

可知 fast 比 slow 多走了一圈 C，推导出 P = X，也就是在快慢指针相遇之后，slow 和 slow2 相遇的地方就是 cycle 的起点。

Code

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

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:
                break

        if not fast or not fast.next:
            return None

        slow2 = head
        while slow != slow2:
            slow = slow.next
            slow2 = slow2.next

        return slow

复杂度

• 时间：$O(n)$
• 空间：$O(1)$