Reorder List

• Create an ArrayList to store the nodes of the linked list.
• Traverse the linked list from the head and add each node to the ArrayList.
• Initialize two pointers, left = 0 and right = list.size() - 1.
• Iterate while left < right:
  • Set the next of the node at index left to point to the node at index right.
  • Increment left.
  • If left becomes equal to right, break the loop (for odd length lists).
  • Set the next of the node at index right to point to the node at the new index left.
  • Decrement right.
• Set the next pointer of the last node in the reordered sequence (at index left) to null.

First, we iterate through the original linked list from head to tail. During this traversal, we add each node to an ArrayList. After the list is fully stored, we can re-wire the next pointers. We use two integer indices, left starting at 0 and right starting at size - 1. We iterate as long as left < right. In each step, we link the node at left to the node at right (nodes.get(left).next = nodes.get(right)). Then, we increment left. To continue the chain, we link the node at right to the new left node (nodes.get(right).next = nodes.get(left)). Then we decrement right. This process continues until the pointers meet or cross. Finally, the next pointer of the last node in the new sequence (which will be at index left when the loop terminates) must be set to null to signify the end of the list.

1import java.util.ArrayList;2import java.util.List;3 4/**5 * Definition for singly-linked list.6 * public class ListNode {7 *     int val;8 *     ListNode next;9 *     ListNode() {}10 *     ListNode(int val) { this.val = val; }11 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }12 * }13 */14class Solution {15    public void reorderList(ListNode head) {16        if (head == null || head.next == null) {17            return;18        }19 20        // 1. Store all nodes in a list21        List<ListNode> nodes = new ArrayList<>();22        ListNode current = head;23        while (current != null) {24            nodes.add(current);25            current = current.next;26        }27 28        // 2. Re-wire the nodes using two pointers29        int left = 0, right = nodes.size() - 1;30        while (left < right) {31            nodes.get(left).next = nodes.get(right);32            left++;33            if (left == right) {34                break;35            }36            nodes.get(right).next = nodes.get(left);37            right--;38        }39        40        // 3. Set the last node's next to null41        nodes.get(left).next = null;42    }43}

• Initialize a class member pointer left to head and a boolean stop to false.
• Define a recursive function recurse(right) that takes the current node as an argument.
• The base case for the recursion is right == null.
• In the recursive step, call recurse(right.next).
• After the recursive call returns, check the stop flag. If true, return immediately.
• Check if the reordering is complete. This happens when left and right pointers meet (for odd-length lists) or left.next points to right (for even-length lists). If so, set the next of the appropriate node to null, set stop to true, and return.
• If not complete, perform the re-wiring:
  • Store left.next in a temporary variable.
  • Set left.next to right.
  • Set right.next to the temporary variable.
  • Advance left to its new position (left = temp).

The core idea is to use the function call stack to our advantage. We define a recursive function that traverses to the end of the list. When the recursion starts to unwind, we are effectively processing nodes from tail to head. We maintain a global or class-level pointer, left, initialized to the head of the list. This pointer will move from the beginning towards the middle. The recursive function takes the current right node as its parameter. The base case is when right is null. After the recursive call recurse(right.next) returns, we are at node right, and the left pointer is at the corresponding node from the beginning. We can then perform the re-wiring. We need a mechanism to stop the re-wiring process once the left and right pointers meet or cross in the middle of the list. A boolean flag or a direct comparison of left and right pointers can be used for this. Once the middle is reached, we terminate the list by setting the next pointer of the middle/last re-wired node to null and signal all parent recursive calls to stop further processing.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    private ListNode left;13    private boolean stop;14 15    public void reorderList(ListNode head) {16        if (head == null || head.next == null) {17            return;18        }19        this.left = head;20        this.stop = false;21        recurse(head);22    }23 24    private void recurse(ListNode right) {25        if (right == null) {26            return;27        }28 29        recurse(right.next);30 31        if (this.stop) {32            return;33        }34 35        if (this.left == right || this.left.next == right) {36            right.next = null;37            this.stop = true;38            return;39        }40 41        ListNode temp = this.left.next;42        this.left.next = right;43        right.next = temp;44        45        this.left = temp;46    }47}

• Find Middle: Use a slow and a fast pointer to find the end of the first half of the list. The slow pointer will be the last node of the first half.
• Split: The node after slow is the head of the second half. Set slow.next = null to break the list into two.
• Reverse: Iteratively reverse the second half of the list.
• Merge: Initialize two pointers, p1 to the head of the first half and p2 to the head of the reversed second half.
• Iterate while p2 is not null:
  • Store the next nodes: temp1 = p1.next, temp2 = p2.next.
  • Link p1 to p2: p1.next = p2.
  • Link p2 to p1's original next: p2.next = temp1.
  • Move pointers forward: p1 = temp1, p2 = temp2.

1. Find the Middle Node: We use the classic "slow and fast pointer" technique. A slow pointer moves one step at a time, while a fast pointer moves two steps. When the fast pointer reaches the end of the list, the slow pointer will be at the middle node (or the end of the first half).

2. Split and Reverse the Second Half: Once the middle is found, we split the list into two halves. The next pointer of the slow node is set to null. The node originally after slow becomes the head of the second half. We then reverse this second half using a standard iterative reversal algorithm (using prev, curr, next pointers).

3. Merge the Two Halves: Now we have two independent lists: the first half starting at head, and the reversed second half. We can merge them by interleaving their nodes. We take one node from the first list, then one from the second, and link them together, advancing the pointers in each list until the second list is exhausted.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public void reorderList(ListNode head) {13        if (head == null || head.next == null) {14            return;15        }16 17        // 1. Find the middle of the list18        ListNode slow = head;19        ListNode fast = head;20        while (fast.next != null && fast.next.next != null) {21            slow = slow.next;22            fast = fast.next.next;23        }24 25        // 2. Reverse the second half of the list26        ListNode secondHead = slow.next;27        slow.next = null; // Split the list28        29        ListNode prev = null;30        ListNode curr = secondHead;31        while (curr != null) {32            ListNode nextNode = curr.next;33            curr.next = prev;34            prev = curr;35            curr = nextNode;36        }37        // 'prev' is now the head of the reversed second half38 39        // 3. Merge the two halves40        ListNode firstHead = head;41        ListNode reversedSecondHead = prev;42        while (reversedSecondHead != null) {43            ListNode temp1 = firstHead.next;44            ListNode temp2 = reversedSecondHead.next;45 46            firstHead.next = reversedSecondHead;47            reversedSecondHead.next = temp1;48 49            firstHead = temp1;50            reversedSecondHead = temp2;51        }52    }53}