MediumBlind75Linked ListTwo PointersStack

Reorder List

You are given the head of a singly linked-list. Reorder the list to be: L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ...

Examples

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

L0=1, Ln=4, L1=2, Ln-1=3 -> 1->4->2->3

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

L0=1, Ln=5, L1=2, Ln-1=4, L2=3 -> 1->5->2->4->3

Constraints

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

Approaches

Store all nodes in an array and reorder by taking from both ends.

CodeT: O(n) | S: O(n)
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
    nodes = []
    curr = head
    while curr:
        nodes.append(curr)
        curr = curr.next
    left, right = 0, len(nodes) - 1
    while left < right:
        nodes[left].next = nodes[right]
        left += 1
        if left == right:
            break
        nodes[right].next = nodes[left]
        right -= 1
    nodes[left].next = None

Find the middle, reverse the second half, then merge the two halves.

CodeT: O(n) | S: O(1)
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
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    prev, curr = None, slow.next
    slow.next = None
    while curr:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    first, second = head, prev
    while second:
        next_first = first.next
        next_second = second.next
        first.next = second
        second.next = next_first
        first = next_first
        second = next_second

Same approach with cleaner code for the merge step.

Diagram

1->2->3->4 Find middle: slow=2, reverse from 3: 4->3 Merge: 1->4->2->3
CodeT: O(n) | S: O(1)
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
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    prev, curr = None, slow.next
    slow.next = None
    while curr:
        curr.next, prev, curr = prev, curr, curr.next
    first, second = head, prev
    while second:
        first.next, first = second, first.next
        second.next, second = first, second.next

Complexity Comparison

Using Array
T: O(n)S: O(n)

Store all nodes in an array and reorder by taking from both ends.

Find Middle + Reverse + Merge
T: O(n)S: O(1)

Find the middle, reverse the second half, then merge the two halves.

Optimized Merge
T: O(n)S: O(1)

Same approach with cleaner code for the merge step.

Common Mistakes

Not finding the correct middle node (off-by-one for odd-length lists)

Losing reference to nodes during the reverse step

Not setting the last node's next to None after reordering

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems