Reorder List medium

Problem Statement

You are given the head of a singly linked list. The list can be represented as:

L0 → L1 → L2 → ... → 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.

Example 1

Input: head = [1,2,3,4] Output: [1,4,2,3]

Example 2

Input: head = [1,2,3,4,5] Output: [1,5,2,4,3]

Steps

  1. Find the middle of the linked list: Use slow and fast pointers to find the middle node.
  2. Reverse the second half of the linked list: Iteratively reverse the linked list starting from the middle node.
  3. Merge the first and reversed second halves: Merge the two halves by interleaving nodes.

Explanation

The algorithm efficiently reorders the linked list in O(n) time and O(1) space. Finding the middle takes linear time, reversing the second half takes linear time, and merging the two halves also takes linear time. The space complexity is constant because we are only using a few pointers, not additional data structures proportional to the input size.

Code

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

def reorderList(head):
    """
    Reorders a linked list in place.

    Args:
      head: The head of the linked list.

    Returns:
      None. Modifies the linked list in place.
    """
    if not head or not head.next:  #Handle empty or single-node lists
        return

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

    # Reverse the second half
    prev = None
    curr = slow.next
    slow.next = None  #Disconnect the first and second halves
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    # Merge the two halves
    head1, head2 = head, prev
    while head2:
        next1 = head1.next
        next2 = head2.next
        head1.next = head2
        head2.next = next1
        head1 = next1
        head2 = next2


#Example Usage
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
reorderList(head)
result = []
while head:
    result.append(head.val)
    head = head.next
print(result) #Output: [1, 4, 2, 3]

head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
reorderList(head)
result = []
while head:
    result.append(head.val)
    head = head.next
print(result) #Output: [1, 5, 2, 4, 3]

Complexity

  • Time Complexity: O(n), where n is the number of nodes in the linked list. Each step (finding the middle, reversing, merging) takes linear time.
  • Space Complexity: O(1). The algorithm uses a constant number of pointers regardless of the input size.