Reorder List

Medium
2009.

Reorder List

Reorder List is a medium coding problem on two pointers, stack and recursion, asked in Amazon, Microsoft, Adobe and Meta interviews.

You are given the head of a singly linked list L0 → L1 → … → Ln-1 → Ln. Reorder it in place to

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

alternating between the front and the back of the list. Only the links may change, not the values. LeetCode's version returns nothing; here, return the head of the reordered list (it is still L0).

Example 1

Input
head = [1,2,3,4]
Output
[1,4,2,3]

Example 2

Input
head = [1,2,3,4,5]
Output
[1,5,2,4,3]
Explanation
The middle node 3 ends up last.

Example 3

Input
head = [7]
Output
[7]

Constraints

  • The number of nodes in the list is in the range [1, 5 * 10^4]
  • 1 <= Node.val <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for singly-linked list (provided by the judge — do not redefine it):
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reorderList = function(head) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Reorder List — Solution in Python, Java & C++

Reorder List solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on two pointers and stack.

Reorder List is a medium coding problem on two pointers, stack and recursion, asked in Amazon, Microsoft, Adobe and Meta interviews.

Problem statement

You are given the head of a singly linked list L0 → L1 → … → Ln-1 → Ln. Reorder it in place to

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

alternating between the front and the back of the list. Only the links may change, not the values. LeetCode's version returns nothing; here, return the head of the reordered list (it is still L0).

Example 1

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
Explanation: The middle node 3 ends up last.

Example 3

Input: head = [7]
Output: [7]

Constraints

  • The number of nodes in the list is in the range [1, 5 * 10^4]
  • 1 <= Node.val <= 1000

Hints for Reorder List

  1. Hint 1

    The result interleaves the first half of the list with the second half read backwards.

  2. Hint 2

    Find the middle with slow and fast pointers, then reverse the second half in place.

  3. Hint 3

    Cut the list after the middle, then merge the two halves by alternately taking one node from each.

How to solve Reorder List

Split, reverse, weave. The front half is read forwards and the back half backwards, so reversing the back half turns the problem into merging two lists by alternation.

Approach

  1. Find the middle: slow = fast = head; while fast.next and fast.next.next exist, move slow one step and fast two.
  2. Reverse the list after slow to get second, and cut with slow.next = null.
  3. Weave: with first = head, while second is not null, save both next pointers, link first.next = second and second.next = savedFirstNext, then advance both.
  4. Return head.

Why it works

The slow pointer stops at the last node of the first half (which has the extra node when the length is odd). After reversing, second lists Ln, Ln-1, … and the weave places each of them right after L0, L1, … in turn, which is exactly the required order; the first half is never shorter, so it absorbs every node of the second.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Forgetting to cut the first half (slow.next = null) leaves a cycle.
  • Pushing all nodes onto a stack also works but costs O(n) extra space.
  • For one or two nodes nothing changes — make sure the loops handle that without special cases.

Reference solution

Python

from typing import Optional

def reorderList(head: Optional[ListNode]) -> Optional[ListNode]:
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    second, prev = slow.next, None
    slow.next = None
    while second:
        second.next, prev, second = prev, second, second.next
    first, second = head, prev
    while second:
        a, b = first.next, second.next
        first.next = second
        second.next = a
        first, second = a, b
    return head

Java

public static ListNode reorderList(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; }
    ListNode cur = slow.next, prev = null;
    slow.next = null;
    while (cur != null) { ListNode nx = cur.next; cur.next = prev; prev = cur; cur = nx; }
    ListNode first = head, second = prev;
    while (second != null) {
        ListNode a = first.next, b = second.next;
        first.next = second;
        second.next = a;
        first = a;
        second = b;
    }
    return head;
}

C++

ListNode* reorderList(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; }
    ListNode *cur = slow->next, *prev = nullptr;
    slow->next = nullptr;
    while (cur) { ListNode* nx = cur->next; cur->next = prev; prev = cur; cur = nx; }
    ListNode *first = head, *second = prev;
    while (second) {
        ListNode *a = first->next, *b = second->next;
        first->next = second;
        second->next = a;
        first = a;
        second = b;
    }
    return head;
}

JavaScript

var reorderList = function(head) {
    var slow = head, fast = head;
    while (fast.next !== null && fast.next.next !== null) { slow = slow.next; fast = fast.next.next; }
    var cur = slow.next, prev = null;
    slow.next = null;
    while (cur !== null) { var nx = cur.next; cur.next = prev; prev = cur; cur = nx; }
    var first = head, second = prev;
    while (second !== null) {
        var a = first.next, b = second.next;
        first.next = second;
        second.next = a;
        first = a;
        second = b;
    }
    return head;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 165 two pointers problems · the whole catalogue

Learn the technique: Two Pointers Technique · Stack Data Structure