143. Reorder List - Explanation

Problem Link

Description

You are given the head of a singly linked-list.

The positions of a linked list of length = 7 for example, can intially be represented as:

[0, 1, 2, 3, 4, 5, 6]

Reorder the nodes of the linked list to be in the following order:

[0, 6, 1, 5, 2, 4, 3]

Notice that in the general case for a list of length = n the nodes are reordered to be in the following order:

[0, n-1, 1, n-2, 2, n-3, ...]

You may not modify the values in the list's nodes, but instead you must reorder the nodes themselves.

Example 1:

Input: head = [2,4,6,8]

Output: [2,8,4,6]

Example 2:

Input: head = [2,4,6,8,10]

Output: [2,10,4,8,6]

Constraints:

  • 1 <= Length of the list <= 1000.
  • 1 <= Node.val <= 1000


Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(1) space, where n is the length of the given list.


Hint 1

A brute force solution would be to store the node values of the list in an array, reorder the values, and create a new list. Can you think of a better way? Perhaps you can try reordering the nodes directly in place, avoiding the use of extra space.


Hint 2

For example, consider the list [1, 2, 3, 4, 5]. To reorder the list, we connect the first and last nodes, then continue with the second and second-to-last nodes, and so on. Essentially, the list is split into two halves: the first half remains as is, and the second half is reversed and merged with the first half. For instance, [1, 2] will merge with the reversed [5, 4, 3]. Can you figure out a way to implement this reordering process? Maybe dividing the list into two halves could help.


Hint 3

We can divide the list into two halves using the fast and slow pointer approach, which helps identify the midpoint of the list. This allows us to split the list into two halves, with the heads labeled as l1 and l2. Next, we reverse the second half (l2). After these steps, we proceed to reorder the two lists by iterating through them node by node, updating the next pointers accordingly.


Company Tags

Please upgrade to NeetCode Pro to view company tags.



1. Brute Force

Intuition

To reorder the linked list in the pattern:

L0 → Ln → L1 → L(n−1) → L2 → ...

A straightforward approach is to store all nodes in an array.
Once stored, we can easily access nodes from both the start and end using two pointers.
By alternately linking nodes from the front (i) and back (j), we can reshape the list in the required order.

Algorithm

  1. Traverse the linked list and push every node into an array.
  2. Initialize two pointers:
    • i = 0 (start)
    • j = len(nodes) - 1 (end)
  3. While i < j:
    • Link nodes[i].next to nodes[j]; increment i.
    • If i >= j, break the loop.
    • Link nodes[j].next to nodes[i]; decrement j.
  4. After the loop, set nodes[i].next = None to terminate the list.
  5. The reordered list is constructed in-place.
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        if not head:
            return

        nodes = []
        cur = head
        while cur:
            nodes.append(cur)
            cur = cur.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

        nodes[i].next = None

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

2. Recursion

Intuition

This recursive approach reorders the list by pairing nodes from the front and back during the recursion unwind phase.

The idea is:

  • Move to the end of the list using recursion.
  • On the way back up (unwinding), connect the current node from the end (cur) to the corresponding node from the front (root).
  • Advance the front pointer (root) step-by-step as recursion unwinds.
  • Stop when the pointers meet or cross.

Recursion naturally processes the list from back to front, making it convenient to match front and back nodes without using extra lists.

Algorithm

  1. Define a recursive function rec(root, cur):
    • cur moves to the end of the list via recursion.
    • root marks the current front node during unwinding.
  2. In the base case:
    • If cur is None, return the front pointer (root).
  3. Recursively call rec on cur.next to reach the tail.
  4. During unwinding:
    • If root meets or crosses cur, set cur.next = None to finish and stop further links.
    • Otherwise:
      • Temporarily save root.next.
      • Link root.next → cur.
      • Link cur.next → temp.
  5. Return the next node (temp) as the updated front pointer.
  6. Start recursion with rec(head, head.next).

This reorders the list in place without extra storage.

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

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:

        def rec(root: ListNode, cur: ListNode) -> ListNode:
            if not cur:
                return root

            root = rec(root, cur.next)
            if not root:
                return None

            tmp = None
            if root == cur or root.next == cur:
                cur.next = None
            else:
                tmp = root.next
                root.next = cur
                cur.next = tmp

            return tmp

        head = rec(head, head.next)

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

3. Reverse And Merge

Intuition

To reorder the list into the pattern
L1 → Ln → L2 → Ln−1 → L3 → Ln−2 → ...,
we can break the problem into three simple steps:

  1. Find the middle of the linked list using slow & fast pointers.
    This splits the list into two halves.

  2. Reverse the second half of the list.
    Doing this makes it easy to merge nodes from the front and back alternately.

  3. Merge the two halves one-by-one:
    Take one node from the first half, then one from the reversed second half, and repeat.

This method is clean, intuitive, and uses only O(1) extra space.

Algorithm

  1. Find the middle:

    • Use slow and fast pointers.
    • When fast reaches the end, slow will be at the midpoint.

  2. Reverse the second half:

    • Start from slow.next.
    • Reverse it using the standard linked-list reversal approach.

  3. Merge the two lists:

    • Take a node from the first half.
    • Take a node from the reversed second half.
    • Continue until the second half is exhausted.

This produces the desired reordered list in-place with no extra memory.

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

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        second = slow.next
        prev = slow.next = None
        while second:
            tmp = second.next
            second.next = prev
            prev = second
            second = tmp

        first, second = head, prev
        while second:
            tmp1, tmp2 = first.next, second.next
            first.next = second
            second.next = tmp1
            first, second = tmp1, tmp2

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1)