Reorder List medium

Problem Statement

Given a singly linked list, group all odd-indexed nodes together followed by the even-indexed nodes. Please note here we are grouping nodes based on their position in the list, and the indexing starts from 1. You may not alter the values in the list's nodes, only nodes themselves may be changed.

Example 1:

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

Example 2:

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

Steps

1. Find the middle of the linked list: Use the slow and fast pointer technique to find the middle node.
2. Reverse the second half of the linked list: Reverse the linked list starting from the middle node.
3. Merge the first and second halves: Interleave the nodes from the first and reversed second halves.

Explanation

The algorithm leverages the slow and fast pointer technique to efficiently find the middle of the linked list. The fast pointer moves twice as fast as the slow pointer. When the fast pointer reaches the end, the slow pointer will be at the middle. Then, we reverse the second half of the list using iterative reversal. Finally, we merge the first and reversed second halves by alternately connecting nodes from each.

Code

class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.next = (next===undefined ? null : next)
    }
}

function reorderList(head: ListNode | null): void {
    if (!head || !head.next) return; //Handle empty or single-node lists

    // Find the middle of the linked list
    let slow = head;
    let fast = head;
    while (fast && fast.next) {
        slow = slow.next!;
        fast = fast.next.next;
    }

    // Reverse the second half
    let prev: ListNode | null = null;
    let curr = slow;
    while (curr) {
        let nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }

    // Merge the first and reversed second halves
    let firstHalf = head;
    let secondHalf = prev;
    while (secondHalf && secondHalf.next) {
        let firstNext = firstHalf.next;
        let secondNext = secondHalf.next;
        firstHalf.next = secondHalf;
        secondHalf.next = firstNext;
        firstHalf = firstNext!;
        secondHalf = secondNext;
    }

    
};

Complexity

• Time Complexity: O(N), where N is the number of nodes in the linked list. We traverse the list multiple times, but each traversal is linear.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space. We are manipulating pointers in place, not creating new data structures proportional to the input size.