Hide sidebar
leetcode/DSA courseSystem Design

Reorder List

Linked ListTwo Pointers
MediumLeetCode #143
20-25 min

Problem Statement

You are given the head of a singly linked-list. The list can be represented as:
L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

Example

Example 1:
Input:
1
2
3
4
Output:
1
4
2
3

Constraints

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

Solution

Approach: Find Middle, Reverse, and Merge

This problem can be solved in three steps: find the middle of the list, reverse the second half, and then merge the two halves.

Reorder Visualization

Step 0: Initial List
1
2
3

Algorithm Steps

  • Find Middle: Use the slow and fast pointer technique to find the middle of the linked list.
  • Reverse Second Half: Reverse the portion of the list that comes after the middle node.
  • Merge: Interleave the nodes from the first and reversed second halves to reorder the list.

Time Complexity: O(n) - We traverse the list three times, which simplifies to O(n).

Space Complexity: O(1) - We modify the list in-place without using extra space.

Find Middle + Reverse + Merge Solution

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

        # Find the middle of the list
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # Reverse the second half
        second = slow.next
        prev = slow.next = None
        while second:
            tmp = second.next
            second.next = prev
            prev = second
            second = tmp
        
        # Merge the two halves
        first, second = head, prev
        while second:
            tmp1, tmp2 = first.next, second.next
            first.next = second
            second.next = tmp1
            first, second = tmp1, tmp2