Back to solutions

Reorder List

MediumLinked List

Reorder a list L0->L1->...->Ln to L0->Ln->L1->Ln-1->... by rearranging nodes in place.

Open problem
Constraints
  • 1 <= size <= 5 * 10^4
  • 1 <= Node.val <= 1000

Find middle, reverse, merge

Time O(n)Space O(1)

Find the midpoint with slow/fast pointers, reverse the second half, then weave the two halves together alternating nodes.

struct ListNode { int val; ListNode* next; };

void reorderList(ListNode* head) {
    if (!head || !head->next) return;
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; }
    ListNode* second = slow->next;
    slow->next = nullptr;
    ListNode* prev = nullptr;
    while (second) { ListNode* nxt = second->next; second->next = prev; prev = second; second = nxt; }
    ListNode* first = head;
    while (prev) {
        ListNode* n1 = first->next; ListNode* n2 = prev->next;
        first->next = prev; prev->next = n1;
        first = n1; prev = n2;
    }
}