LeetCode 143 - Reorder List

The problem gives us the head of a singly linked list and asks us to reorder the nodes in a very specific alternating pattern. A normal linked list looks like this: We must transform it into: The important detail is that we are not allowed to change node values.

leetcodemediumlinked-listtwo-pointersstackrecursion

LeetCode Problem 143

Difficulty: šŸŸ” Medium
Topics: Linked List, Two Pointers, Stack, Recursion

Solution

Problem Understanding

The problem gives us the head of a singly linked list and asks us to reorder the nodes in a very specific alternating pattern.

A normal linked list looks like this:

L0 ā†’ L1 ā†’ L2 ā†’ ... ā†’ Ln

We must transform it into:

L0 ā†’ Ln ā†’ L1 ā†’ Ln-1 ā†’ L2 ā†’ Ln-2 ā†’ ...

The important detail is that we are not allowed to change node values. We must physically rearrange the node connections by modifying the next pointers.

For example:

1 ā†’ 2 ā†’ 3 ā†’ 4

becomes:

1 ā†’ 4 ā†’ 2 ā†’ 3

Another example:

1 ā†’ 2 ā†’ 3 ā†’ 4 ā†’ 5

becomes:

1 ā†’ 5 ā†’ 2 ā†’ 4 ā†’ 3

The input is the head node of a singly linked list. The function modifies the list in-place and does not return anything.

The constraints tell us that the list can contain up to 5 * 10^4 nodes. This immediately rules out inefficient quadratic solutions. Since linked lists do not support random access, repeatedly traversing to the end of the list would become too slow.

Several edge cases are important:

  • A list with only one node should remain unchanged.
  • A list with two nodes is already in valid reordered form.
  • Odd-length lists and even-length lists behave slightly differently during splitting and merging.
  • Since the list is singly linked, we cannot move backward, so reversing or accessing the tail requires careful pointer manipulation.
  • Forgetting to terminate the reordered list can accidentally create cycles.

Approaches

Brute Force Approach

A straightforward approach is to repeatedly take the last node and insert it after the current front node.

For example:

1 ā†’ 2 ā†’ 3 ā†’ 4 ā†’ 5

First iteration:

1 ā†’ 5 ā†’ 2 ā†’ 3 ā†’ 4

Second iteration:

1 ā†’ 5 ā†’ 2 ā†’ 4 ā†’ 3

To do this in a singly linked list, we must repeatedly traverse the list to find the second-last node so we can detach the last node.

This works correctly because every iteration places the correct node from the end into its required position.

However, this approach is inefficient. Each extraction of the last node requires traversing most of the remaining list. Since this happens many times, the total time complexity becomes quadratic.

With up to 50,000 nodes, an O(n^2) solution is too slow.

Optimal Approach

The key insight is that the reordered sequence alternates between:

  • nodes from the beginning
  • nodes from the end

Instead of repeatedly searching for the tail, we can reorganize the list into two halves:

  1. Find the middle of the list.
  2. Reverse the second half.
  3. Merge the two halves alternately.

For example:

1 ā†’ 2 ā†’ 3 ā†’ 4 ā†’ 5

After finding the middle:

First half:  1 ā†’ 2 ā†’ 3
Second half: 4 ā†’ 5

Reverse the second half:

5 ā†’ 4

Merge alternately:

1 ā†’ 5 ā†’ 2 ā†’ 4 ā†’ 3

This works efficiently because:

  • finding the middle takes O(n)
  • reversing takes O(n)
  • merging takes O(n)

The total time complexity becomes linear.

Approach Time Complexity Space Complexity Notes
Brute Force O(nĀ²) O(1) Repeatedly traverses to the tail
Optimal O(n) O(1) Split, reverse, and merge the list

Algorithm Walkthrough

  1. Find the middle of the linked list using the slow and fast pointer technique.

The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. When fast reaches the end, slow will be at the middle.

Example:

1 ā†’ 2 ā†’ 3 ā†’ 4 ā†’ 5
        ^
      slow
  1. Split the list into two halves.

After locating the middle, disconnect the first half from the second half.

First half:  1 ā†’ 2 ā†’ 3
Second half: 4 ā†’ 5
  1. Reverse the second half.

Reverse the nodes in the second half using standard linked list reversal.

4 ā†’ 5

becomes:

5 ā†’ 4

Reversal is important because the reorder pattern alternates from the front and the back. 4. Merge the two halves alternately.

Start with the first node of the first half, then attach one node from the reversed second half.

Example merge process:

First half:  1 ā†’ 2 ā†’ 3
Second half: 5 ā†’ 4

Step-by-step merge:

1 ā†’ 5
1 ā†’ 5 ā†’ 2 ā†’ 4
1 ā†’ 5 ā†’ 2 ā†’ 4 ā†’ 3
  1. Ensure the final node points to None.

This prevents accidental cycles in the linked list.

Why it works

The algorithm works because the reordered pattern is essentially an alternating merge between the first half of the list and the reversed second half. Reversing the second half places the tail nodes in the exact order needed for alternating insertion. Since every node is visited and repositioned exactly once, the final structure matches the required ordering.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

from typing import Optional

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """

        if not head or not head.next:
            return

        # Step 1: Find the middle
        slow = head
        fast = head

        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        # Step 2: Reverse second half
        second_half = slow.next
        slow.next = None

        prev = None
        current = second_half

        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node

        second_half = prev

        # Step 3: Merge two halves
        first_half = head

        while second_half:
            temp1 = first_half.next
            temp2 = second_half.next

            first_half.next = second_half
            second_half.next = temp1

            first_half = temp1
            second_half = temp2

The implementation follows the three major phases of the algorithm.

The first phase finds the midpoint using slow and fast pointers. The loop condition fast.next and fast.next.next ensures that slow stops at the correct midpoint for both odd and even length lists.

The second phase reverses the second half in-place. Three pointers are used:

  • prev stores the reversed portion
  • current traverses the remaining nodes
  • next_node temporarily stores the next node before changing pointers

After reversal, prev becomes the new head of the reversed half.

The final phase merges the two lists alternately. Temporary pointers preserve the next nodes before rewiring the links. This prevents losing access to the remaining portions of the lists.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reorderList(head *ListNode) {
    if head == nil || head.Next == nil {
        return
    }

    // Step 1: Find middle
    slow := head
    fast := head

    for fast.Next != nil && fast.Next.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

    // Step 2: Reverse second half
    secondHalf := slow.Next
    slow.Next = nil

    var prev *ListNode
    current := secondHalf

    for current != nil {
        nextNode := current.Next
        current.Next = prev
        prev = current
        current = nextNode
    }

    secondHalf = prev

    // Step 3: Merge two halves
    firstHalf := head

    for secondHalf != nil {
        temp1 := firstHalf.Next
        temp2 := secondHalf.Next

        firstHalf.Next = secondHalf
        secondHalf.Next = temp1

        firstHalf = temp1
        secondHalf = temp2
    }
}

The Go implementation is structurally almost identical to the Python version. The primary difference is explicit pointer handling with *ListNode.

Go uses nil instead of Python's None. Variable declarations are also more explicit. Since linked list manipulation is pointer-based in both languages, the overall logic remains the same.

No integer overflow concerns exist because the algorithm does not perform arithmetic operations beyond pointer traversal.

Worked Examples

Example 1

Input:

1 ā†’ 2 ā†’ 3 ā†’ 4

Step 1: Find Middle

slow fast
1 1
2 3

Middle node is 2.

Split:

First half:  1 ā†’ 2
Second half: 3 ā†’ 4

Step 2: Reverse Second Half

Before reversal:

3 ā†’ 4

After reversal:

4 ā†’ 3

Step 3: Merge

First Half Second Half Result
1 ā†’ 2 4 ā†’ 3 1 ā†’ 4
2 3 1 ā†’ 4 ā†’ 2 ā†’ 3

Final result:

1 ā†’ 4 ā†’ 2 ā†’ 3

Example 2

Input:

1 ā†’ 2 ā†’ 3 ā†’ 4 ā†’ 5

Step 1: Find Middle

slow fast
1 1
2 3
3 5

Middle node is 3.

Split:

First half:  1 ā†’ 2 ā†’ 3
Second half: 4 ā†’ 5

Step 2: Reverse Second Half

Before reversal:

4 ā†’ 5

After reversal:

5 ā†’ 4

Step 3: Merge

First Half Second Half Result
1 ā†’ 2 ā†’ 3 5 ā†’ 4 1 ā†’ 5
2 ā†’ 3 4 1 ā†’ 5 ā†’ 2 ā†’ 4
3 None 1 ā†’ 5 ā†’ 2 ā†’ 4 ā†’ 3

Final result:

1 ā†’ 5 ā†’ 2 ā†’ 4 ā†’ 3

Complexity Analysis

Measure Complexity Explanation
Time O(n) Finding middle, reversing, and merging each traverse the list once
Space O(1) Only a few pointer variables are used

The algorithm performs three separate linear traversals of the linked list. Since constants are ignored in asymptotic analysis, the total time complexity remains O(n).

The solution modifies the list in-place and does not allocate extra data structures proportional to input size, so the space complexity is constant.

Test Cases

# Helper functions for testing

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    dummy = ListNode()
    current = dummy

    for value in values:
        current.next = ListNode(value)
        current = current.next

    return dummy.next

def list_to_array(head):
    result = []

    while head:
        result.append(head.val)
        head = head.next

    return result

class Solution:
    def reorderList(self, head):
        if not head or not head.next:
            return

        slow = head
        fast = head

        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        second_half = slow.next
        slow.next = None

        prev = None
        current = second_half

        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node

        second_half = prev
        first_half = head

        while second_half:
            temp1 = first_half.next
            temp2 = second_half.next

            first_half.next = second_half
            second_half.next = temp1

            first_half = temp1
            second_half = temp2

# Test 1: Even number of nodes
head = build_list([1, 2, 3, 4])
Solution().reorderList(head)
assert list_to_array(head) == [1, 4, 2, 3]  # standard even-length case

# Test 2: Odd number of nodes
head = build_list([1, 2, 3, 4, 5])
Solution().reorderList(head)
assert list_to_array(head) == [1, 5, 2, 4, 3]  # standard odd-length case

# Test 3: Single node
head = build_list([1])
Solution().reorderList(head)
assert list_to_array(head) == [1]  # minimal input

# Test 4: Two nodes
head = build_list([1, 2])
Solution().reorderList(head)
assert list_to_array(head) == [1, 2]  # already correctly ordered

# Test 5: Three nodes
head = build_list([1, 2, 3])
Solution().reorderList(head)
assert list_to_array(head) == [1, 3, 2]  # smallest meaningful reorder

# Test 6: Larger list
head = build_list([1, 2, 3, 4, 5, 6])
Solution().reorderList(head)
assert list_to_array(head) == [1, 6, 2, 5, 3, 4]  # larger even-length list

# Test 7: Duplicate values
head = build_list([1, 1, 1, 1])
Solution().reorderList(head)
assert list_to_array(head) == [1, 1, 1, 1]  # duplicate values

print("All tests passed!")
Test Why
[1,2,3,4] Validates standard even-length behavior
[1,2,3,4,5] Validates standard odd-length behavior
[1] Tests minimum input size
[1,2] Ensures already valid structure remains correct
[1,2,3] Tests smallest non-trivial reorder
[1,2,3,4,5,6] Verifies larger even-length merge correctness
[1,1,1,1] Ensures logic depends on nodes, not values

Edge Cases

Single Node List

A list containing only one node is already in valid reordered form. This case can easily cause issues if the algorithm blindly attempts to split or reverse the list. The implementation handles this immediately with:

if not head or not head.next:
    return

This prevents unnecessary pointer operations.

Odd-Length Lists

Odd-length lists contain a middle node that should remain at the end of the reordered structure.

Example:

1 ā†’ 2 ā†’ 3 ā†’ 4 ā†’ 5

becomes:

1 ā†’ 5 ā†’ 2 ā†’ 4 ā†’ 3

The middle node 3 stays at the end. Incorrect midpoint handling can duplicate or lose this node. The slow-fast pointer technique ensures the split occurs correctly.

Preventing Cycles

One of the most common linked list bugs is accidentally creating a cycle.

If we do not disconnect the first half before reversing:

slow.next = None

the original links may remain connected, causing infinite traversal loops after merging.

Explicitly terminating the first half guarantees a proper final structure.

Two-Node Lists

A two-node list is already correctly ordered:

1 ā†’ 2

Some implementations mistakenly reverse or reconnect pointers unnecessarily, potentially breaking the list. The current solution naturally handles this case without special logic because the second half contains only one node and the merge phase remains valid.