Zip Linked List

Tags

Zip Linked List

Category

Linked Lists

Difficulty

Hard

Problem Statement

Given a singly linked list, rearrange its nodes by interleaving nodes from the beginning and end. Specifically, the first node is followed by the last node, then the second node followed by the second-to-last node, and so on. For a list 1 -> 2 -> 3 -> 4 -> 5 -> 6, the result would be 1 -> 6 -> 2 -> 5 -> 3 -> 4. The rearrangement should be done in place.

Intuition

This problem combines three fundamental linked list operations: (1) finding the middle of the list, (2) reversing the second half, and (3) interleaving (merging) the two halves. After splitting and reversing, we have two shorter lists that we merge by alternating nodes from each.

Approach

  1. Find the middle of the linked list using the slow/fast pointer technique.
  2. Split the list into two halves at the middle. The first half runs from head to the middle node, and the second half starts after the middle.
  3. Reverse the second half of the list.
  4. Interleave the two halves: take one node from the first half, then one from the reversed second half, alternating until both halves are exhausted.
  5. Return the head of the resulting list.

Pseudocode

function zipLinkedList(head):
    if head is null or head.next is null:
        return head

    // Step 1: Find middle
    slow = head
    fast = head

    while fast is not null and fast.next is not null:
        slow = slow.next
        fast = fast.next.next

    // Step 2: Split at middle
    secondHalf = slow.next
    slow.next = null

    // Step 3: Reverse second half
    secondHalf = reverseList(secondHalf)

    // Step 4: Interleave
    first = head
    second = secondHalf

    while first is not null and second is not null:
        firstNext = first.next
        secondNext = second.next

        first.next = second
        second.next = firstNext

        first = firstNext
        second = secondNext

    return head

function reverseList(head):
    prev = null
    current = head
    while current is not null:
        next = current.next
        current.next = prev
        prev = current
        current = next
    return prev

Time & Space Complexity

  • Time: O(n) where n is the number of nodes. Finding the middle takes O(n/2), reversing takes O(n/2), and interleaving takes O(n/2). Total: O(n).
  • Space: O(1) extra space. All operations are performed in place with a constant number of pointers.

Key Insights

  • The three-step decomposition (split, reverse, merge) is a powerful pattern that appears in many linked list problems.
  • The slow/fast pointer technique gives the midpoint in a single pass without knowing the length.
  • For odd-length lists, the first half gets the extra node; this is natural since the middle node stays in place.
  • Saving next pointers before rewiring is critical to avoid losing references during interleaving.
  • This is sometimes called "folding" a linked list — conceptually, you fold the list in half and zip the two sides together.

Edge Cases

  • Empty list — return null.
  • Single node — return the node unchanged.
  • Two nodes — already zipped (first, last are adjacent).
  • Odd-length list — the first half has one more node than the second; after interleaving, the extra node naturally appears at the end.
  • Even-length list — both halves are the same length and interleave perfectly.
  • All nodes have the same value — the structure changes but output values look the same.

Linked mentions