Advanced Linked List Interview Patterns: Reversal, Cycle Detection, and Merge Operations (2025)

Why Linked Lists in 2025?

Linked list problems test pointer manipulation, in-place operations with O(1) space, and the two-pointer (fast/slow) technique. They appear regularly at FAANG and mid-size companies. The patterns are reusable: the fast/slow pointer pattern solves cycle detection, finding the middle, and the k-th from end. The reversal technique solves palindrome check, reverse in groups, and reorder list. Mastering ~5 patterns covers the vast majority of linked list interview questions.

Pattern 1: Fast/Slow Pointers (Floyd’s Algorithm)

Two pointers: slow moves 1 step, fast moves 2 steps. If a cycle exists, fast and slow will meet. If no cycle, fast reaches null first. Find middle: when fast reaches end, slow is at the middle (useful for palindrome check, merge sort on lists).

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

def find_cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None  # no cycle
    # Reset slow to head; both move 1 step
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    return slow  # cycle start

def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

Cycle start proof: if the cycle starts at distance k from head, and the cycle has length c, then when slow enters the cycle, fast is k steps ahead (modulo c). After c – (k mod c) more steps, both meet. Resetting slow to head and moving both 1 step brings them to the cycle start in k more steps.

Pattern 2: In-Place Reversal

Reverse a linked list in O(1) space: maintain prev, curr, next. Advance one node at a time, pointing curr.next backward.

def reverse_list(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev  # new head

def reverse_k_group(head, k):
    # LC 25: Reverse Nodes in k-Group
    dummy = ListNode(0, head)
    group_prev = dummy
    while True:
        kth = get_kth(group_prev, k)
        if not kth: break
        group_next = kth.next
        # Reverse the group
        prev, curr = kth.next, group_prev.next
        while curr != group_next:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        tmp = group_prev.next
        group_prev.next = kth
        group_prev = tmp
    return dummy.next

def get_kth(curr, k):
    while curr and k > 0:
        curr = curr.next
        k -= 1
    return curr

Pattern 3: Merge Sorted Lists and Merge Sort

Merge two sorted lists: standard merge step from merge sort. O(n+m) time, O(1) space (modify next pointers in place).

def merge_two_lists(l1, l2):
    dummy = ListNode(0)
    curr = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1; l1 = l1.next
        else:
            curr.next = l2; l2 = l2.next
        curr = curr.next
    curr.next = l1 or l2
    return dummy.next

def merge_k_lists(lists):
    # LC 23: Merge k Sorted Lists — use min-heap
    import heapq
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
    dummy = curr = ListNode(0)
    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = node; curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

Pattern 4: Reorder List and LRU Cache

Reorder List (LC 143): L0→L1→…→Ln-1→Ln to L0→Ln→L1→Ln-1→L2→…. Steps: (1) Find middle with fast/slow. (2) Reverse the second half. (3) Merge the two halves by alternating nodes. Each step is O(n), O(1) space. LRU Cache (LC 146): doubly linked list + hash map. Map: key → node (O(1) lookup). Linked list: nodes in LRU order (head = most recent, tail = least recent). Get: move node to head. Put: add to head; if capacity exceeded, remove tail. Both operations O(1). The dummy head and tail nodes simplify edge cases (no null checks on remove).

{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”How does Floyd's cycle detection algorithm work?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Floyd's algorithm uses two pointers: slow (moves 1 step) and fast (moves 2 steps). If a cycle exists, fast laps slow and they eventually meet inside the cycle. If no cycle, fast reaches null first. To find the cycle start after detecting a meeting point: reset slow to head, keep fast at the meeting point, and move both 1 step at a time. They meet at the cycle start. This works because the meeting point is exactly k steps from the cycle start (where k is the distance from head to cycle start).”}},{“@type”:”Question”,”name”:”How do you reverse a linked list in k-groups (LC 25)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use a dummy node before the head. Maintain group_prev (the node before the current group). Find the k-th node from group_prev. If it exists: reverse the k nodes in the group using the standard three-pointer reversal (prev, curr, next), then reconnect the reversed group to group_prev and the next group. Advance group_prev to what was the first node of the group (now the last after reversal). Repeat until fewer than k nodes remain.”}},{“@type”:”Question”,”name”:”How do you implement an LRU Cache in O(1) get and put?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use a doubly linked list and a hash map. The list maintains access order: the most recently used node is at the head, least recently used at the tail. The map stores key → node for O(1) lookup. On get: look up the node, move it to head, return value. On put: if key exists, update value and move to head. If new and at capacity, remove the tail node (LRU eviction) and remove its key from the map, then add the new node to the head. Both operations are O(1).”}},{“@type”:”Question”,”name”:”How do you merge k sorted linked lists efficiently?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use a min-heap of size k. Initialize with the first node of each list. Repeatedly: pop the minimum node, add it to the result list, and push that node's next node onto the heap (if it exists). Time complexity: O(n log k) where n is the total number of nodes across all lists, since each node is pushed and popped from the heap once, and heap operations are O(log k).”}},{“@type”:”Question”,”name”:”What is the fast/slow pointer trick for finding the middle of a linked list?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Initialize both slow and fast to head. Move slow 1 step and fast 2 steps each iteration. When fast reaches the end (fast is null or fast.next is null), slow is at the middle. For even-length lists, slow lands on the second middle node. This is used as the split point in merge sort on linked lists and as the first step in palindrome linked list check (find middle, reverse second half, compare).”}}]}