We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

Reorder List

Difficulty: Medium

Problem Description

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 → …

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Key Insights

The problem requires reordering a linked list in a specific way without changing node values.
This can be achieved using a two-pointer approach to find the middle of the list, followed by reversing the second half and merging the two halves.
The time complexity needs to be efficient given the constraints, ideally O(n).
Care must be taken to maintain the linked list structure and avoid cycles.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can follow these steps:

Use the two-pointer technique (slow and fast pointers) to find the middle of the linked list.
Split the linked list into two halves.
Reverse the second half of the linked list.
Merge the two halves in the required order by alternating nodes from each half.

Data Structures and Algorithmic Approaches:

Linked List: To represent the input and output.
Two Pointers: To find the middle of the list.
Reversal: To reverse the second half of the list before merging.
Merging: To combine the two halves in the specified order.

Code Solutions

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reorderList(head):
    if not head or not head.next:
        return
    
    # Step 1: Find the middle of the list
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    # Step 2: Split the list into two halves
    second = slow.next
    slow.next = None  # End the first half
    first = head
    
    # Step 3: Reverse the second half
    prev = None
    while second:
        next_node = second.next
        second.next = prev
        prev = second
        second = next_node
    
    # Step 4: Merge the two halves
    second = prev  # This is the head of the reversed second half
    while second:
        temp1, temp2 = first.next, second.next
        first.next = second
        second.next = temp1
        first = temp1
        second = temp2

← Back to All Questions