How do you solve Reorder List on LeetCode?

Reorder List (LeetCode #143) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Understanding linked list traversal is crucial for solving this problem.

What is the brute force solution for Reorder List?

The brute force approach for Reorder List is Brute Force, with O(n²) time complexity and O(n) space complexity. The brute force approach involves creating a new list where we manually rearrange the nodes based on the required order. This is straightforward but inefficient as it requires multiple traversals of the linked list. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Reorder List?

Reorder List uses the following concepts: Linked List, Two Pointers, Stack, Recursion. The recommended patterns to study are: Two Pointers, Linked List Reversal, Merging Linked Lists.

What are the interview tips for Reorder List?

Always clarify whether you can modify the list structure or just the values. Think about edge cases, such as lists with an odd number of nodes. Practice explaining your thought process while coding; it helps in interviews.

What are common mistakes when solving Reorder List?

Not properly handling the end of the merged list, leading to cycles. Forgetting to set the last node's next pointer to null.

#143

Reorder List

Medium

Linked ListTwo PointersStackRecursionTwo PointersLinked List ReversalMerging Linked Lists

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(n)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal approach involves finding the middle of the list, reversing the second half, and then merging the two halves together. This is efficient and uses less space.

⚙️

Algorithm

3 steps

1Step 1: Find the middle of the linked list using the slow and fast pointer technique.
2Step 2: Reverse the second half of the linked list.
3Step 3: Merge the two halves by alternating nodes from each half.

solution.py29 lines

1# Full working Python code
2class ListNode:
3    def __init__(self, val=0, next=None):
4        self.val = val
5        self.next = next
6
7def reorderList(head):
8    if not head:
9        return
10    # Step 1: Find the middle
11    slow, fast = head, head
12    while fast and fast.next:
13        slow = slow.next
14        fast = fast.next.next
15    # Step 2: Reverse the second half
16    prev, curr = None, slow
17    while curr:
18        next_temp = curr.next
19        curr.next = prev
20        prev = curr
21        curr = next_temp
22    # Step 3: Merge the two halves
23    first, second = head, prev
24    while second.next:
25        temp1, temp2 = first.next, second.next
26        first.next = second
27        second.next = temp1
28        first, second = temp1, temp2
29    first.next = None

ℹ

Complexity note: The time complexity is O(n) because we traverse the linked list a few times. The space complexity is O(1) since we only use a few pointers.

1Understanding linked list traversal is crucial for solving this problem.
2Recognizing the need to reverse part of the list is key to optimizing the solution.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.