Reorder List

Problem Link

143. Reorder List – LeetCode

Problem Statement

You are given the head of a singly linked list.
Reorder the list such that:

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ...

You must do this in-place without altering the nodes’ values.

Examples

Example 1:

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2:

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

Constraints

• The number of nodes in the list is in the range [1, 5 * 10⁴]

• 1 <= Node.val <= 1000

Intuition

The goal is to rearrange the linked list so that the first element is followed by the last, then second by second-last, and so on.

This can be done in three main steps:

1. Find the middle of the list using slow/fast pointers.

2. Reverse the second half of the list.

3. Merge the two halves alternately.

Approach

1. Use the slow and fast pointer technique to find the middle.

2. Reverse the second half starting from the middle.

3. Merge the first half and the reversed second half in an alternating pattern.

Java Code

class Solution {

    // Step 1: Reverse a linked list
    public ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextNode = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextNode;
        }
        return prev;
    }

    // Step 2: Merge two lists alternately
    public void merge(ListNode list1, ListNode list2) {
        while (list2 != null) {
            ListNode next1 = list1.next;
            ListNode next2 = list2.next;

            list1.next = list2;
            if (next1 == null) break;

            list2.next = next1;

            list1 = next1;
            list2 = next2;
        }
    }

    // Step 3: Main function to reorder list
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;

        // Find middle node
        ListNode slow = head;
        ListNode fast = head;
        ListNode prev = null;

        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        // Split the list into two halves
        prev.next = null;

        // Reverse the second half
        ListNode l2 = reverse(slow);

        // Merge both halves
        merge(head, l2);
    }
}

Time and Space Complexity

Dry Run

Input:

List: 1 → 2 → 3 → 4 → 5

Step 1: Find mid → Node 3
Step 2: Reverse second half → 5 → 4
Step 3: Merge →

1 → 5 → 2 → 4 → 3

Conclusion

This is a three-step linked list pattern problem that combines slow-fast pointer, reversal, and alternate merging techniques. It’s a common interview question testing mastery over linked list manipulation in-place.