Framework Thinking - Neetcode 150 - Reorder Linked List
Here is solutions for Reorder Linked List.
1. Understand the problem
You are given the head of a singly linked list:
L0 -> L1 -> L2 -> ... -> Ln-1 -> Ln
Re-order it to:
L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ...
2. Clarify Constraints (Ask 4–5 Questions)
- Is modifying the node values allowed?
- No, must modify only pointers.
- What is the expected time & space complexity?
- Optimal is O(n) time and O(1) extra space.
- What about edge cases?
-
Empty list -> return None
-
One node -> unchanged
-
Two nodes -> unchanged
-
Three nodes -> reorder to center.
- Is input always a valid linked list?
- Yes.
- Any memory constraints?
- Yes, must use constant extra space.
3. Explore Examples
| Input | Output |
|---|---|
| 1 -> 2 -> 3 -> 4 | 1 -> 4 -> 2 -> 3 |
| 1 -> 2 -> 3 -> 4 -> 5 | 1 -> 5 -> 2 -> 4 -> 3 |
| 1 | 1 |
| 1 -> 2 | 1 -> 2 |
4. Brainstorm 2 - 3 solutions
4.1. Naive Solution - Time O(N), Space O(N)
-
Store nodes to list
-
Use two-pointer merge and reconstruct
-
Time: O(n) + reconstruct -> O(n)
-
Space: O(n) -> Not optimal.
4.2. Fast/Slow Pointer + Reverse + Merge
-
Find middle using fast and slow pointers
-
Reverse second half
-
Merge alternating nodes
-
Time: O(n)
-
Space: O(1)
5. Implement solutions
5.1. Naive solutions - Time O(N), Space O(N)
-
Idea: Store address of node to index in array (i, address of node), everything is about address.
-
Apply two pointer i, j from start and end of the array => build a linked list.
# 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: O(N).
-
Space: O(N).
5.2. Recursion - Time O(N), Space O(N)
Key idea:
-
The solution uses recursion to simulate two pointers:
-
Forward pointer -> represents root (starts from the head, moves forward only when recursion unwinds).
-
Backward pointer -> represents cur (moves from tail to head as recursion unwinds).
def rec(root: ListNode, cur: ListNode) -> ListNode:
if not cur:
return root
root = rec(root, cur.next)
=> Move curr to the end of the list, head is the start of the list, continue to each meet with each other.
# 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: O(N).
-
Space: O(N).
5.3. Reverse Half Linked List And Merge - Time: O(N), Space O(1)
# 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: O(N).
-
Space: O(1).
6. Dry run examples
- Step 1: Find Middle using Fast & Slow
1 -> 2 -> 3 -> 4 -> 5
First half: 1 -> 2 -> 3
Second half: 4 -> 5
- Step 2: Reverse Second Half
First half: 1 -> 2 -> 3
Second half: 5 -> 4 -> None
- Step 3: Merge Two Halves
1 -> 5 -> 2 -> 4 -> 3 -> None