Reorder List – 143. LeetCode

In the “Reorder List” problem, you’re given a singly linked list, and the goal is to rearrange it such that the first element is followed by the last element, then the second element by the second-to-last, and so on. For example, given a list 1 -> 2 -> 3 -> 4, the reordered list would be 1 -> 4 -> 2 -> 3.

This problem involves restructuring the linked list while maintaining its nodes and order constraints. It’s a popular interview question because it tests understand of linked list manipulation, pointer management, and efficiency.

Brute Force Approach

import java.util.*;

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

        // Store all nodes in a list
        List<ListNode> nodes = new ArrayList<>();
        ListNode current = head;
        while (current != null) {
            nodes.add(current);
            current = current.next;
        }

        // Rearrange the list
        int i = 0, j = nodes.size() - 1;
        while (i < j) {
            nodes.get(i).next = nodes.get(j);
            i++;
            if (i < j) {
                nodes.get(j).next = nodes.get(i);
                j--;
            }
        }
        nodes.get(i).next = null; // Terminate the reordered list
    }
}

• Store Nodes in a List:
  • Traverse the linked list and store its nodes in an array for direct access by index.
• Reorder Using Two Pointers:
  • Use two pointers (i and j) to select nodes from the front and back of the list and reconnect them in the desired order.
• Update Pointers:
  • Reassign the next pointers of the nodes to form the reordered list.

Optimal Solution

• Pattern: Two Pointers and Reversal

• Key Steps:

1. Use two pointers to split the list into two halves.

2. Reverse the second half of the list.

3. Merge the two halves.

The linked list structure allows us to manipulate pointers directly without extra space. By splitting, reversing, and merging the list, we achieve the desired order efficiently:

1. Splitting ensures we process the two halves independently.

2. Reversing the second half aligns it for merging with the first half.

3. Merging interleaves nodes from the two halves.

Algorithm Steps

1. Find the Middle of the List:

• Use the slow and fast pointer technique to find the midpoint.

2. Reverse the Second Half:

• Reverse the second half of the list starting from the middle.

3. Merge the Two Halves:

• Alternately merge nodes from the first and reversed second half.

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

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

        // Step 2: Reverse the second half
        ListNode prev = null, current = slow.next;
        slow.next = null; // Split the list into two halves
        while (current != null) {
            ListNode nextNode = current.next;
            current.next = prev;
            prev = current;
            current = nextNode;
        }

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

Line-By-Line Explanation

Step 1: Base Case

if (head == null || head.next == null) return;

• Checks if the list is empty (head == null) or has only one node (head.next == null). If so, no reordering is needed.
• Short circuits processing when it’s unnecessary, adhering to efficiency standard.

Step 2: Find the Middle of the List

ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}

• Uses slow and fast pointer technique to find the middle of the linked list.
• The slow pointer moves one step at a time, while the fast pointer moves two steps. When fast reaches the end, slow points to the middle.

Step 2: Reverse the Second Half of the List

ListNode prev = null, current = slow.next;
slow.next = null; // Split the list into two halves
while (current != null) {
    ListNode nextNode = current.next;
    current.next = prev;
    prev = current;
    current = nextNode;
}

• Starts from the node after slow (the second half of the list).
• Reverses the second half by manipulating pointers:
  • current.next = prev reverses the direction of the pointer
  • prev becomes the new head of the reversed second half.
• The second half must be reversed to interleave nodes from both ends of the list during the merge step.

Step 3: Merge the Two Halves

ListNode first = head, second = prev;
while (second != null) {
    ListNode temp1 = first.next, temp2 = second.next;
    first.next = second;
    second.next = temp1;
    first = temp1;
    second = temp2;
}

• Initialization: first points to the head of the first half, and second points to the head of the reversed second half.
• Interleaving:
  • first.next = second: Connects the next node of the first half to the current node of the reversed second half.
  • second.next = temp1: Connects the next node of the reversed second half to the next node of the first half.
• Progresses first and second pointers to their respective next nodes.

Why This Code Works

This code follows LeetCode best practices by:

1. Leveraging Linked List Properties: Uses pointer manipulation instead of auxiliary data structures.

2. Optimal Efficiency: Achieves  O(n)  time and  O(1)  space complexity.

3. Clear, Modular Logic: Splits the solution into logical steps (find middle, reverse, merge), making it easy to understand and debug.