mediumLinked List

Reorder List

Reorder a linked list by alternating the first remaining node and the last remaining node.

LeetCode ↗

Work through the cases

3 examples

Input notation

A nonempty line of list values.

Expected result

Reordered values separated by spaces.

Case 1

Input

1 2 3 4 5

Expected output

1 5 2 4 3

Case 2

Input

1 2 3 4

Expected output

1 4 2 3

Case 3

Input

Expected output

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Reorder as L_0 → L_n → L_1 → L_{n-1} × s. An array of pointers is O(n) space. n ≤ 5 × 10^4. The second half must be reversed and woven into the first: find the midpoint with two pointers, cut, reverse the second half, and merge alternately. Three linear passes, in place.

We first use fast and slow pointers to find the midpoint of the linked list, then reverse the second half of the list, and finally merge the two halves.

The time complexity is O(n), where n is the length of the linked list. The space complexity is O(1).

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode cur = slow.next;
        slow.next = null;

        ListNode pre = null;
        while (cur != null) {
            ListNode t = cur.next;
            cur.next = pre;
            pre = cur;
            cur = t;
        }
        cur = head;

        while (pre != null) {
            ListNode t = pre.next;
            pre.next = cur.next;
            cur.next = pre;
            cur = pre.next;
            pre = t;
        }
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.