DSA Series Day 22 Reorder List in Java, Python and Rust

DSA Series Day 22: Reorder List in Java, Python and Rust

Reorder List is a favourite linked list interview question, and Day 22 of the Tekraze DSA series uses it to close out the linked list chapter. It isn’t one big trick. It is three small tricks glued together: find the middle of a list, reverse a list and merge two lists. If you followed Day 18, Reverse Linked List, Day 19, Merge Two Sorted Lists and Day 20, Linked List Cycle, you already own most of the pieces.

Also Read: Day 21, Remove Nth Node From End of List to warm up the slow and fast pointer idea this problem starts with.

What is the Reorder List problem?

You get the head of a singly linked list L0 -> L1 -> … -> Ln. Rearrange it in place so it reads L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> …. You may not change the values inside the nodes, only the links between them.

This is LeetCode problem 143, so you can also test your answer on the official Reorder List page on LeetCode.

text

Input:  1 -> 2 -> 3 -> 4
Output: 1 -> 4 -> 2 -> 3
Input:  1 -> 2 -> 3 -> 4 -> 5
Output: 1 -> 5 -> 2 -> 4 -> 3

How should you think about Reorder List in plain words?

Picture taking cards alternately from the top and the bottom of a deck. The top half is easy because we already walk forward from the head. The bottom half is the hard part, since a singly linked list can’t walk backwards.

So we flip the bottom half around, and then it also reads from the front. Now we zip the two halves together like a jacket zipper.

DSA Series Day 22: Reorder List in Java, Python and Rust 1
DSA Series Day 22: Reorder List in Java, Python and Rust 7

Here is the whole Reorder List idea on the list 1 -> 2 -> 3 -> 4 -> 5:

text

Start:             1 -> 2 -> 3 -> 4 -> 5
1. Find middle:    slow stops at 3
2. Cut + reverse:  1 -> 2 -> 3     and     5 -> 4
3. Merge:          1 -> 5 -> 2 -> 4 -> 3

What does the brute force approach to Reorder List look like?

Copy every node into an array. Then use two indexes, one from the start and one from the end, and relink the nodes in the alternating order.

python

def reorder_brute(head):
    nodes = []
    while head:
        nodes.append(head)
        head = head.next
    i, j = 0, len(nodes) - 1
    while i < j:
        nodes[i].next = nodes[j]
        i += 1
        if i == j:
            break
        nodes[j].next = nodes[i]
        j -= 1
    if nodes:
        nodes[i].next = None

This runs in O(n) time but needs O(n) extra space for the array. Interviewers usually ask for the O(1) space version next.

How do we get the optimal Reorder List solution?

Do it in three steps:

  1. Find the middle. Use slow and fast pointers. When fast can’t jump two more nodes, slow is at the end of the first half.
  2. Reverse the second half. Cut the list after slow, then reverse everything that comes after the cut.
  3. Merge the halves. Take one node from the first half, then one from the reversed second half, and repeat until the second half runs out.

Time is O(n) because each step walks the list at most once. Space is O(1) since we only move a few pointers and never copy nodes. If you want a refresher on why these bounds hold, read our Big O helper post on time and space complexity.

Reorder List three step flow of splitting, reversing and merging a list
DSA Series Day 22: Reorder List in Java, Python and Rust 8

Reorder List in Java

java

import java.util.*;
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}
public class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        // 1. Find the middle with slow and fast pointers.
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 2. Reverse the second half.
        ListNode prev = null, cur = slow.next;
        slow.next = null;
        while (cur != null) {
            ListNode nxt = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nxt;
        }
        // 3. Merge the two halves one by one.
        ListNode first = head, second = prev;
        while (second != null) {
            ListNode n1 = first.next, n2 = second.next;
            first.next = second;
            second.next = n1;
            first = n1;
            second = n2;
        }
    }
    static ListNode build(int[] vals) {
        ListNode dummy = new ListNode(0), tail = dummy;
        for (int v : vals) { tail.next = new ListNode(v); tail = tail.next; }
        return dummy.next;
    }
    static List<Integer> toList(ListNode head) {
        List<Integer> out = new ArrayList<>();
        for (ListNode c = head; c != null; c = c.next) out.add(c.val);
        return out;
    }
    public static void main(String[] args) {
        int[][] in = {{1, 2, 3, 4}, {1, 2, 3, 4, 5}, {1}, {1, 2}, {1, 2, 3}, {}};
        String[] want = {"[1, 4, 2, 3]", "[1, 5, 2, 4, 3]", "[1]", "[1, 2]", "[1, 3, 2]", "[]"};
        Solution s = new Solution();
        for (int i = 0; i < in.length; i++) {
            ListNode h = build(in[i]);
            s.reorderList(h);
            String got = toList(h).toString();
            if (!got.equals(want[i])) throw new AssertionError(got + " != " + want[i]);
            System.out.println(Arrays.toString(in[i]) + " -> " + got);
        }
        System.out.println("All Java tests passed");
    }
}

Reorder List in Python

The line cur.next, prev, cur = prev, cur, cur.next looks odd, but Python builds the right-hand tuple first and then assigns, so it reverses one link safely. The Python reference on assignment statements explains the order.

Reorder List mistake where a missing cut creates a loop in the nodes
DSA Series Day 22: Reorder List in Java, Python and Rust 9

python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def reorder_list(head):
    if not head or not head.next:
        return
    # 1. Find the middle with slow and fast pointers.
    slow = fast = head
    while fast.next and fast.next.next:
        slow, fast = slow.next, fast.next.next
    # 2. Reverse the second half.
    prev, cur = None, slow.next
    slow.next = None
    while cur:
        cur.next, prev, cur = prev, cur, cur.next
    # 3. Merge the two halves one by one.
    first, second = head, prev
    while second:
        n1, n2 = first.next, second.next
        first.next = second
        second.next = n1
        first, second = n1, n2
def build(vals):
    dummy = tail = ListNode()
    for v in vals:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next
def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out
if __name__ == "__main__":
    tests = [([1, 2, 3, 4], [1, 4, 2, 3]), ([1, 2, 3, 4, 5], [1, 5, 2, 4, 3]),
             ([1], [1]), ([1, 2], [1, 2]), ([1, 2, 3], [1, 3, 2]), ([], [])]
    for vals, want in tests:
        h = build(vals)
        reorder_list(h)
        got = to_list(h)
        assert got == want, (vals, got, want)
        print(vals, "->", got)
    print("All Python tests passed")

Reorder List in Rust

Rust won’t let a slow and a fast reference share a Box list, so the Rust version counts the length first and walks to the end of the first half with one mutable reference. It then takes the second half with Option::take, reverses it and weaves it back in. It is still O(n) time and O(1) extra space. If linked lists in Rust interest you, Learning Rust With Entirely Too Many Linked Lists is the best deep dive.

rust

#[derive(Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}
pub fn reorder_list(head: &mut Option<Box<ListNode>>) {
    // 1. Count the nodes and cut the list after the first half.
    let mut len = 0;
    let mut cur = head.as_ref();
    while let Some(node) = cur {
        len += 1;
        cur = node.next.as_ref();
    }
    if len < 3 {
        return;
    }
    let mut tail = head.as_mut().unwrap();
    for _ in 0..(len - 1) / 2 {
        tail = tail.next.as_mut().unwrap();
    }
    let mut rest = tail.next.take();
    // 2. Reverse the second half.
    let mut rev: Option<Box<ListNode>> = None;
    while let Some(mut node) = rest {
        rest = node.next.take();
        node.next = rev;
        rev = Some(node);
    }
    // 3. Weave the reversed half into the first half.
    let mut first = head.as_mut();
    while let Some(node) = first {
        if let Some(mut r) = rev {
            rev = r.next.take();
            r.next = node.next.take();
            node.next = Some(r);
            first = node.next.as_mut().unwrap().next.as_mut();
        } else {
            break;
        }
    }
}
fn build(vals: &[i32]) -> Option<Box<ListNode>> {
    let mut head = None;
    for &v in vals.iter().rev() {
        head = Some(Box::new(ListNode { val: v, next: head }));
    }
    head
}
fn to_vec(mut head: &Option<Box<ListNode>>) -> Vec<i32> {
    let mut out = vec![];
    while let Some(node) = head {
        out.push(node.val);
        head = &node.next;
    }
    out
}
fn main() {
    let tests: Vec<(Vec<i32>, Vec<i32>)> = vec![
        (vec![1, 2, 3, 4], vec![1, 4, 2, 3]),
        (vec![1, 2, 3, 4, 5], vec![1, 5, 2, 4, 3]),
        (vec![1], vec![1]),
        (vec![1, 2], vec![1, 2]),
        (vec![1, 2, 3], vec![1, 3, 2]),
        (vec![], vec![]),
    ];
    for (vals, want) in tests {
        let mut h = build(&vals);
        reorder_list(&mut h);
        let got = to_vec(&h);
        assert_eq!(got, want);
        println!("{:?} -> {:?}", vals, got);
    }
    println!("All Rust tests passed");
}

All three programs ran the even example 1 to 4, the odd example 1 to 5, a single node, two nodes, three nodes and an empty list. Every check passed in Java, Python and Rust.

What are the 6 best tips for an easy Reorder List solution?

  1. Spot the pattern. When an answer mixes the front and the back of a list, think: find the middle, reverse the back half, then merge.
  2. Break it into helpers. Write three tiny pieces: middle, reverse and merge. Each one is a problem you have already solved, and bugs are much easier to find.
  3. Cut the list. Always set slow.next = null before reversing, or the two halves stay joined and you get a loop.
  4. Merge until the second half ends. The first half is the same length or one longer, so looping while the second half exists covers both odd and even lengths.
  5. Check the edge cases. An empty list, one node and two nodes should come back unchanged.
  6. Explain before you code. In an interview, say the array idea for Reorder List in one line, then describe the three step plan before you write anything. It shows you see the structure.

What are the common mistakes people make in Reorder List?

  • Forgetting to cut the first half, which creates a cycle after merging.
  • Using the wrong loop condition for the middle and putting the extra node in the second half.
  • Losing the next pointers during the merge because they were not saved first.
  • Swapping node values instead of relinking nodes, which the problem forbids.
  • Returning a new head even though the problem changes the list in place.

Most wrong Reorder List answers on interview platforms come from the first mistake on this list, so check the cut before anything else.

Where does the Reorder List pattern show up in practice?

Pairing the front of a sequence with the back is a pattern, not a product feature. A feed that alternates the oldest and newest items could be built with the same idea. The bigger lesson is to split a hard task into small, well known steps. Code that reshapes data streams, like merging sorted log files or reversing a buffer, uses the same building blocks.

Final thoughts on Reorder List

Reorder List teaches you to stop fighting a hard problem and break it into three easy ones. Once you can find the middle, reverse a half and merge two lists, this question stops being scary. Re-solve it from memory tomorrow, without looking at the code, and you will own it.

Which earlier posts in the series should you read?

New to the series? Start at the DSA series hub. Here is the path that leads to today’s problem:

Keep our data structures cheat sheet handy for a quick look at how linked lists compare with arrays, stacks and queues.

Frequently asked questions

What is the Reorder List problem?

You rearrange a singly linked list L0, L1, up to Ln into the order L0, Ln, L1, Ln-1 and so on, in place, by changing links and not values.

How do you solve Reorder List in O(1) space?

Find the middle with slow and fast pointers, cut the list there, reverse the second half, then merge the two halves by alternating one node from each.

What is the time and space complexity of Reorder List?

The optimal solution runs in O(n) time and O(1) extra space. The array based solution is also O(n) time but uses O(n) space.

Why do we reverse the second half?

A singly linked list can only move forward. Reversing the second half lets us read the last nodes first, so we can pair them with the front nodes.

Can I swap values instead of moving nodes?

No. The problem asks you to change the node links, not the values, so value swapping is not accepted in interviews.

Content Protection by DMCA.com
Spread the love
Scroll to Top
×