LeetCode Solution 143 - Reorder List

Problem Statement

Given the head of a singly linked list, reorder the list to follow the pattern:

• The first node is followed by the last node.
• The second node is followed by the second last node, and so on.

It should be done in-place without modifying the node values.

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]

---

Optimal Approach: Reverse the Second Half & Merge

Steps:

1. Find the middle of the linked list using slow & fast pointers.
2. Reverse the second half of the list.
3. Merge the two halves.

This approach ensures an O(N) time complexity and O(1) space complexity.

---

C++ Solution (LeetCode-Compatible)

class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next || !head->next->next) return;
        
        // Step 1: Find the middle
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // Step 2: Reverse the second half
        ListNode* prev = nullptr;
        ListNode* curr = slow->next;
        slow->next = nullptr;
        while (curr) {
            ListNode* nextNode = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextNode;
        }
        
        // Step 3: Merge the two halves
        ListNode* first = head;
        ListNode* second = prev;
        while (second) {
            ListNode* temp1 = first->next;
            ListNode* temp2 = second->next;
            first->next = second;
            second->next = temp1;
            first = temp1;
            second = temp2;
        }
    }
};

---

Step-by-Step Explanation

1. Find Middle: Use two pointers, slow and fast. Slow moves one step, fast moves two steps. When fast reaches the end, slow is at the middle.
2. Reverse Second Half: Reverse the list starting from slow->next.
3. Merge Lists: Interleave the two halves by adjusting pointers.

---

Dry Run Example

Given:

1 -> 2 -> 3 -> 4 -> 5

Step 1: Find Middle: slow points at 3.

Step 2: Reverse Second Half:

5 -> 4 -> NULL

Step 3: Merge Two Halves:

1 -> 5 -> 2 -> 4 -> 3

---

Alternative Approaches & Why Not?

1. Brute Force:

• Store nodes in an array and rearrange using extra space.
• Time Complexity: O(N), Space Complexity: O(N). ❌

2. Using Stack:

• Push half the elements into a stack and reorder.
• Time Complexity: O(N), Space Complexity: O(N). ❌

3. Two Pointers (Optimal Approach - Used Above):

• Time Complexity: O(N), Space Complexity: O(1). ✅

---

Complexity Analysis

Approach	Time Complexity	Space Complexity
Brute Force	O(N)	O(N)
Stack-Based	O(N)	O(N)
Two Pointers (Optimal)	O(N)	O(1)

---

Conclusion

• The two-pointer approach provides the best efficiency.
• This method ensures an O(N) time complexity with O(1) space complexity.

Similar Problems for Practice:

• Reverse Linked List
• Merge Two Sorted Lists
• Palindrome Linked List