Reordering a Linked List

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.

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]

Naive Approach

1. Traverse the linked list and store the nodes in an array.
2. Use two pointers, one starting from the beginning and the other from the end of the array.
3. Reorder the linked list by alternating nodes from the beginning and the end of the array.

Code (Python):

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

def reorderListNaive(head):
    if not head:
        return

    nodes = []
    curr = head
    while curr:
        nodes.append(curr)
        curr = curr.next

    i, j = 0, len(nodes) - 1
    while i < j:
        nodes[i].next = nodes[j]
        i += 1
        if i >= j:
            break
        nodes[j].next = nodes[i]
        j -= 1

    nodes[i].next = None  # set the last node's next to None

Time Complexity: O(N), where N is the number of nodes in the linked list.

Space Complexity: O(N), because we store all nodes in an array.

Optimal Approach

1. Find the middle of the linked list using the slow and fast pointer approach.
2. Reverse the second half of the linked list.
3. Merge the first half and the reversed second half.

Code (Python):

def reorderListOptimal(head):
    if not head or not head.next:
        return

    # 1. Find middle
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # 2. Reverse second half
    prev, curr = None, slow.next
    slow.next = None  # break the list into two halves
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    # 3. Merge two halves
    first, second = head, prev
    while second:
        temp1, temp2 = first.next, second.next
        first.next = second
        second.next = temp1
        first, second = temp1, temp2

Time Complexity: O(N), where N is the number of nodes in the linked list. Finding the middle, reversing the second half, and merging take O(N) time.

Space Complexity: O(1), because we are doing it in place.

Edge Cases

• Empty linked list: The function should return without any changes.
• Single-node linked list: The function should return without any changes.
• Two-node linked list: The function should swap the nodes.