LeetCode Solutions Blog

Reorder List

Number: 143

Difficulty: Medium

Paid? No

Problem Description

Given the head of a singly linked list, reorder it in-place such that the new node order is: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → … You cannot modify the node values; only rearrange the nodes themselves.

Key Insights

Find the middle of the linked list using the fast and slow pointer technique.
Reverse the second half of the list.
Merge the two halves, alternating nodes from the first half and the reversed second half.
The challenge is done in-place, ensuring a linear time solution with constant extra space.

Space and Time Complexity

Time Complexity: O(n) – Each of the three main steps (finding the middle, reversing, merging) takes O(n) time. Space Complexity: O(1) – The algorithm is done in-place with only a few pointers.

Solution

The solution involves three key steps:

Use two pointers (slow and fast) to identify the middle of the list.
Reverse the second half of the list. This can be done iteratively by adjusting the next pointers.
Merge the two lists: One starting from the head and the other from the head of the reversed second half. Interleave the nodes by alternating between the two lists until complete. This approach uses in-place pointer manipulation, thus ensuring no extra space is used aside from a few temporary variables.

Code Solutions

# 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: ListNode) -> None:
        if not head or not head.next:
            return
        
        # Step 1: Find the middle of the linked list using slow and fast pointers.
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # Step 2: Reverse the second half of the list.
        prev, curr = None, slow.next
        slow.next = None  # Split the list into two halves.
        while curr:
            next_temp = curr.next   # Save next node.
            curr.next = prev        # Reverse current pointer.
            prev = curr             # Move prev to current.
            curr = next_temp        # Move to the next node.
        
        # Step 3: Merge the two halves, alternating nodes.
        first, second = head, prev
        while second:
            temp1 = first.next  # Save next node from first half.
            temp2 = second.next # Save next node from reversed second half.
            first.next = second # Link first node to second list node.
            second.next = temp1 # Link second node to the next node in first half.
            first = temp1       # Move pointer in first half.
            second = temp2      # Move pointer in second half.