Reorder List

Naive Approach

A straightforward but less efficient approach involves storing the linked list nodes in an auxiliary data structure like an array. This allows for easy access to nodes from both ends, facilitating the reordering process.

1. Store Nodes in an Array: Traverse the linked list and store each node in an array.
2. Reorder from Array: Use two pointers, one starting from the beginning and the other from the end of the array. Alternately pick nodes from both ends and relink them.

Code (Python)

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

def reorderList_naive(head):
    if not head or not head.next:
        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 # Important: Null-terminate the list

Time Complexity

• O(N) to traverse the linked list and store nodes in the array.
• O(N) to reorder the linked list from the array.

Overall: O(N).

Space Complexity

• O(N) to store the linked list nodes in the array.

Optimal Approach

A more efficient approach involves three main steps:

1. Find the Middle: Use the slow and fast pointer technique to find the middle of the linked list.
2. Reverse the Second Half: Reverse the linked list starting from the middle.
3. Merge Two Halves: Merge the first half and the reversed second half.

Code (Python)

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

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

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

    second_half = prev

    # 3. Merge two halves
    first_half = head
    while second_half:
        temp1 = first_half.next
        temp2 = second_half.next

        first_half.next = second_half
        second_half.next = temp1

        first_half = temp1
        second_half = temp2

Time Complexity

• O(N) to find the middle of the linked list.
• O(N/2) which is O(N) to reverse the second half of the linked list.
• O(N) to merge the two halves.

Overall: O(N).

Space Complexity

• O(1) constant space.

Edge Cases

• Empty List: If the input list is empty (head is None), the function should return without doing anything.
• Single Node List: If the list contains only one node (head.next is None), there's nothing to reorder, so the function should return.
• Even vs. Odd Length: The algorithm should correctly handle both even and odd length linked lists.