24. Swap Nodes in Pairs

Problem: Swap adjacent nodes in a linked list pairwise, returnnig the new head. Do not modify node values—only rewire nodes.

Approaches:

1. Iterative: Use a dummy head to track the previous node. Adjust pointers for each pair.
2. Recursive: Swap the first two nodes, then recurce on the reamining list.

class Solution:    
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(next=head)
        prev = dummy
        curr = head
        while curr and curr.next:
            next_node = curr.next
            next_next = next_node.next
            prev.next = next_node
            next_node.next = curr
            curr.next = next_next
            prev = curr
            curr = next_next
        return dummy.next

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        first = head
        second = head.next
        first.next = self.swapPairs(second.next)
        second.next = first
        return second

19. Remove Nth Node From End of List

Problem: Remove the nth node from the end of a linked list and return the head.

Approaches:

1. Iterative (Length Calculation): Compute the list length, then find the node before the target to remove.
2. Two Pointers: Let a fast pointer lead by n+1 steps, then move both until fast reaches the end. The slow pointer will be at the node before the target.

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(next=head)
        length = 0
        current = head
        while current:
            length += 1
            current = current.next
        prev = dummy
        for _ in range(length - n):
            prev = prev.next
        prev.next = prev.next.next
        return dummy.next

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(next=head)
        slow = fast = dummy
        for _ in range(n + 1):
            fast = fast.next
        while fast:
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return dummy.next

面试题 02.07. Intersection of Two Linked Lists

Problem: Find the intersection node of two linked lists (or null if none). Preserve the original list structure.

Approach: Calculate lengths of both lists. Adjust pointers to start at the same relative position, then traverse until nodes match.

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        len_a, len_b = 0, 0
        curr_a, curr_b = headA, headB
        while curr_a:
            curr_a = curr_a.next
            len_a += 1
        while curr_b:
            curr_b = curr_b.next
            len_b += 1
        curr_a, curr_b = headA, headB
        if len_a > len_b:
            for _ in range(len_a - len_b):
                curr_a = curr_a.next
        else:
            for _ in range(len_b - len_a):
                curr_b = curr_b.next
        while curr_a != curr_b:
            curr_a = curr_a.next
            curr_b = curr_b.next
        return curr_a

142. Linked List Cycle II

Problem: Return the first node where a linked list starts looping (or null if no cycle). Do not modify the list.

Approach: Use fast/slow pointers. When they meet, reset slow to head and move both at the same speed—their next meeting is the cycle start (derived from 2(x+y) = x+y + n(y+z) → x = (n-1)(y+z) + z).

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