Techniques

• Use of the dummy pointer, to avoid dealing with empty pointers
  • Use when needed to create a new linked list

Types of questions

Find kth element

• Use fast and slow pointers, move the fast pointer by k first

Find mid element

• while fast and fast.next
• Move fast pointer at two time speed

Find starting point of cycle

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        fast, slow = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                break
        if not fast or not fast.next:
            return None
        slow = head 
        while slow != fast:
            fast = fast.next
            slow = slow.next
        return slow

Find common index

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        # p1 指向 A 链表头结点，p2 指向 B 链表头结点
        p1, p2 = headA, headB
        while p1 != p2:
            # p1 走一步，如果走到 A 链表末尾，转到 B 链表
            p1 = p1.next if p1 else headB
            # p2 走一步，如果走到 B 链表末尾，转到 A 链表
            p2 = p2.next if p2 else headA
        return p1