Linked List Manipulation

Why do we use a linked list, say over an array? Their true power comes from the ability to manipulate pointers. You can break, reconnect, and reorder nodes in a way that is not possible with static structures like arrays. Inorder to solve linked list problems, you must learn the art of re-wiring a list as required.

Here is a problem to test of your linked list skills. It can be broken down into several smaller, fundamental patterns. Try to map out the steps on paper before looking ahead.

Problem: Reorder List LeetCode Link : Given a linked list, reorder it in a specific way: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ... 💡 Hint

To solve this challenge, you need to apply a series of transformations on the linked list.

1. Finding the Middle (Fast & Slow Pointers)

If you haven't already read the Tortoise and Hare chapter, please do so now. The chapter talks about using fast and slow pointers on arrays, but the same principle applies to linked lists.

2. In-Place List Reversal

This is one of the fundamental linked list manipulation patterns. The idea is to maintain 3 pointers while traversing the list: prev, curr, and next. In each iteration you will update the next pointer of curr to point to prev, effectively reversing the direction of the link.

curr

def reverse_list(head):
    prev = None
    curr = head
    while curr:
        next = curr.next  # Store next node
        curr.next = prev       # Reverse the link
        prev = curr            # Move prev to current
        curr = next       # Move to next node
    return prev  # New head of the reversed list

// The classic iterative reversal
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
    ListNode next = curr.next; // Store next
    curr.next = prev;              // Reverse
    prev = curr;                   // Advance prev
    curr = next;               // Advance curr
}
return prev; // New head

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr != nullptr) {
        ListNode* next = curr->next; // Store next
        curr->next = prev;            // Reverse
        prev = curr;                  // Advance prev
        curr = next;                  // Advance curr
    }
    return prev; // New head
}

3. Merging Two Lists

This involves creating a new list by picking nodes from two other lists. You typically maintain a pointer to the head of each list and a tail pointer for the new merged list. At each step, you decide which node to append to the tail and advance its corresponding pointer.

Pro tip: This same idea is used in k-way merging problems, where you merge multiple sorted lists into one. Always pick the smallest node from the heads of the lists and append it to the merged list. Use a min-heap for efficiency when merging k lists.

Walkthrough: Solving "Reorder List"

Now, let's solve our challenge by combining our three tools in a clear, three-step process:

Find the middle of the list: Use the Fast & Slow Pointer pattern to find the start of the second half of the list.
Reverse the second half: We take the second half of the list (starting from the middle node) and apply the In-Place List Reversal pattern to it. Now we have two distinct lists: the first half and the reversed second half.
Merge the two halves: We "weave" the two lists together. We take the first node from the first half, then the first node from the second half, then the second node from the first half, and so on, carefully re-wiring their next pointers until the second list is exhausted.

def reorder_list(head):
    if not head or not head.next:
        return

    # Step 1: Find the middle of the list
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next

    # Step 2: Reverse the second half of the list
    second_half_head = slow.next
    slow.next = None  # Split the list
    
    prev = None
    curr = second_half_head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    second = prev # `prev` is now the head of the reversed second half

    # Step 3: Merge the two halves
    first = head
    while second:
        temp1, temp2 = first.next, second.next
        first.next = second
        second.next = temp1
        first, second = temp1, temp2

public void reorderList(ListNode head) {
    if (head == null || head.next == null) {
        return;
    }

    // Step 1: Find the middle of the list
    ListNode slow = head;
    ListNode fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // Step 2: Reverse the second half of the list
    ListNode secondHalf = slow.next;
    ListNode prev = null;
    slow.next = null; // Split the list into two halves
    
    ListNode current = secondHalf;
    while (current != null) {
        ListNode nextTemp = current.next;
        current.next = prev;
        prev = current;
        current = nextTemp;
    }
    ListNode second = prev; // `prev` is now the head of the reversed second half

    // Step 3: Merge the two halves
    ListNode first = head;
    while (second != null) {
        ListNode temp1 = first.next;
        ListNode temp2 = second.next;
        first.next = second;
        second.next = temp1;
        first = temp1;
        second = temp2;
    }
}

void reorderList(ListNode* head) {
    if (!head || !head->next) {
        return;
    }

    // Step 1: Find the middle of the list
    ListNode *slow = head, *fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // Step 2: Reverse the second half
    ListNode* second_half_head = slow->next;
    slow->next = nullptr; // Split the list

    ListNode* prev = nullptr;
    ListNode* curr = second_half_head;
    while (curr) {
        ListNode* next_temp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next_temp;
    }
    ListNode* second = prev;

    // Step 3: Merge the two halves
    ListNode* first = head;
    while (second) {
        ListNode* temp1 = first->next;
        ListNode* temp2 = second->next;
        first->next = second;
        second->next = temp1;
        first = temp1;
        second = temp2;
    }
}

Complexity Analysis

Time Complexity: $O(N)$ Finding the middle is $O(N)$ . Reversing the second half is $O(N/2)$ , which is still $O(N)$ . Merging the two halves is another $O(N)$ . Overall, the complexity is linear.