Reorder List: Rearranging Nodes in a Linked List

The "Reorder List" problem is a unique challenge in linked list manipulation, involving the reordering of nodes in a specific pattern.

Problem Statement

Given a singly linked list, reorder it such that the list follows the pattern: first node, last node, second node, second last node, and so on.

Example

• Input: Linked List 1 -> 2 -> 3 -> 4
• Output: Reordered List 1 -> 4 -> 2 -> 3

Solution Approach

Breaking Down the Solution

• Find Middle: Use the fast and slow pointer technique to find the middle of the list.
• Reverse Second Half: Reverse the second half of the list starting from the middle.
• Merge Halves: Alternately merge nodes from the first half and the reversed second half.

Conclusion

The Reorder List problem is an excellent exercise in linked list operations, combining techniques like finding the middle of a list, reversing a list, and merging lists. It showcases complex manipulation of data structures and is a useful skill for many algorithmic challenges.

Rust Solution

Rust's borrow checker makes a pointer-linked list painful, so this keeps every Node in one Vec<Node> and links them by Option<usize> index instead of by reference — the classic arena trick, with head itself an Option<usize>. nodes[slow].next.take() moves a link out and leaves None behind in a single step, which sidesteps borrowing nodes mutably twice while re-splicing the halves. Iteration unwraps each index with while let Some(ci) = cur, and the whole store is threaded through as &mut Vec<Node> so all three phases mutate the same backing Vec.

Go Solution

Go keeps the idiomatic pointer-linked list — Next *ListNode — because nil is a first-class zero value: var prev *ListNode starts nil with no initialiser and the head == nil guard reads naturally. Tuple assignment drives both the two-pointer walk (slow, fast := head, head) and the merge setup (first, second := head, prev), while reorderList returns nothing and simply mutates through the pointers. The helpers lean on slice idioms: range over v, a &ListNode{} dummy head that removes the first-node special case, and append(res, h.Val) growing a nil res slice — Go hands back nil rather than an empty slice for an empty list.