Reorder List

medium linked list two pointers

Problem

Given the head of a singly linked list L: L0 → L1 → … → Ln-1 → Ln, reorder it in place to L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → … using O(1) extra space.

Three phases: (1) find the middle with slow/fast pointers, (2) reverse the second half in place, (3) walk both halves and splice them together one node at a time.

Input1 → 2 → 3 → 4 → 5

Output1 → 5 → 2 → 4 → 3

list (comma-separated)

def reorder_list(head):
    # 1. find middle
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    # 2. reverse second half
    prev, cur = None, slow.next
    slow.next = None
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    # 3. merge the two halves
    first, second = head, prev
    while second:
        t1, t2 = first.next, second.next
        first.next = second
        second.next = t1
        first, second = t1, t2

function reorderList(head) {
  let slow = head, fast = head;
  while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
  let prev = null, cur = slow.next;
  slow.next = null;
  while (cur) {
    const nxt = cur.next;
    cur.next = prev;
    prev = cur;
    cur = nxt;
  }
  let first = head, second = prev;
  while (second) {
    const t1 = first.next, t2 = second.next;
    first.next = second;
    second.next = t1;
    first = t1;
    second = t2;
  }
}

class Solution {
    public void reorderList(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
        ListNode prev = null, cur = slow.next;
        slow.next = null;
        while (cur != null) {
            ListNode nxt = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nxt;
        }
        ListNode first = head, second = prev;
        while (second != null) {
            ListNode t1 = first.next, t2 = second.next;
            first.next = second;
            second.next = t1;
            first = t1;
            second = t2;
        }
    }
}

void reorderList(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
    ListNode *prev = nullptr, *cur = slow->next;
    slow->next = nullptr;
    while (cur) {
        ListNode* nxt = cur->next;
        cur->next = prev;
        prev = cur;
        cur = nxt;
    }
    ListNode *first = head, *second = prev;
    while (second) {
        ListNode *t1 = first->next, *t2 = second->next;
        first->next = second;
        second->next = t1;
        first = t1;
        second = t2;
    }
}

Explanation

The target pattern interleaves the list from both ends: first, last, second, second-to-last, and so on. The trick is to do this in three phases — find the middle, reverse the back half, then zip the two halves together.

Phase 1 uses slow/fast pointers: fast moves twice as fast, so when it reaches the end, slow is at the middle. Phase 2 reverses the second half in place with the standard prev/nxt pointer flip, so prev becomes the head of the reversed back half.

Phase 3 walks first from the front and second from the reversed back, splicing one node from each alternately. Saving t1 and t2 before relinking keeps us from losing the rest of either half.

Example: 1 → 2 → 3 → 4 → 5. The middle is 3; the back half 4 → 5 reverses to 5 → 4. Zipping front 1 → 2 → 3 with 5 → 4 gives 1 → 5 → 2 → 4 → 3.

Everything is done by re-pointing links, so it meets the O(1) extra space requirement in a few linear passes.

Time: O(n) Space: O(1)