Reorder a list: L0, Ln, L1, Ln-1, …

Rearrange a list into the zigzag order L0, Ln, L1, Ln-1, … by splitting it in half, reversing the back half, and weaving the two together.

The idea

Find the middle, cut the list there, reverse the second half, then zip the two halves together one node at a time, alternating first half, second half. That turns a straight list into L0, Ln, L1, Ln-1, … without any extra memory.

Code

public static void Reorder(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
    ListNode second = Reverse(slow.next);
    slow.next = null;
    ListNode p1 = head, p2 = second;
    while (p2 != null) {
        ListNode n1 = p1.next, n2 = p2.next;
        p1.next = p2; p2.next = n1;
        p1 = n1; p2 = n2;
    }
}

Tips

• Cut with slow.next = null before reversing, or the reversal walks straight past the cut into the part you already handled.
• The weave loop only has to check p2, because the first half is never shorter than the second.

In the .NET library

This chains three classic sub-patterns: fast/slow to find the middle, in-place reversal, and a merge that alternates by position instead of by value.