单链表小结 + LeetCode 142

Singly Linked List

不能通过 index 在 \(O(1)\) 时间访问元素, 而必须从头开始找, 平均花费 \(O(n)\) 时间.
插入元素时只需要 \(O(1)\) 时间, 而列表则需要移动所有的后继元素.
在删除元素时, 找 next node 很容易, 但是找 previous node 则需要从头开始, 平均需要 \(O(n)\) 时间. 双链表就只需要 \(O(1)\).

Two Pointer Technique

LeetCode 142. Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Note: Do not modify the linked list.

Slow pointer 每次移动 1 步, fast pointer 每次移动 2 步, 从 head 同时出发.
记环的入口 index 为 \(e\) (entrance), 第一次相遇时 index 为 \(m\) (meeting), 环的长度为 \(l\) (loop length).
则到入口时, fast pointer 比 slow pointer 快了 \(e \bmod l\) 步, 则
\[ m = (e - 1) + [l - (e \bmod l)]. \]

相遇后把 fast pointer 扔掉, 同时让另一个 slow pointer 从 head 开始跑, 则新 slow pointer 到入口时, 比老的慢
\[ [(m + e) - (e - 1)] \bmod l = 0. \]

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

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return        

        slow = head
        fast = head

        while True:
            
            slow = slow.next
            fast = fast.next.next if fast.next else None
            
            if not fast:
                return
            if slow == fast:
                slow2 = head
                while slow != slow2:
                    slow = slow.next
                    slow2 = slow2.next
                return slow

Tips

• Always examine if the node is null before you call the next field.
  Getting the next node of a null node will cause the null-pointer error. For example, before we run fast = fast.next.next, we need to examine both fast and fast.next is not null.

if not head:
    return 

• Other classic problems
  21 Merge Two Sorted Lists
  138 Copy List with Random Pointer
  206 Reverse Linked List

单链表小结 + LeetCode 142

原文：https://www.cnblogs.com/shiina922/p/11138773.html