Odd Even Linked List medium

Problem Statement

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

The first node is considered odd, the second node is even, and so on.

Note that the relative order inside both the odd and even groups should remain as it was in the input.

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

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. Handle Empty or Single Node List: If the list is empty or has only one node, return the head directly as no rearrangement is needed.

2. Initialize Pointers: Create two pointers, odd and even, both initially pointing to the head. odd will track the odd-indexed nodes, and even will track the even-indexed nodes. We'll also need a pointer evenHead to keep track of the beginning of the even sublist.

3. Iterate and Relink: Iterate through the list. In each iteration:

   • Update the odd pointer to point to the next odd node (jumping over one node).
   • Update the even pointer to point to the next even node.
   • If there are remaining even nodes, link the current even node to the next node. This handles the case of odd numbers of nodes.

4. Concatenate Odd and Even Lists: After the iteration, concatenate the end of the odd list to the beginning of the even list.

5. Return the Reordered List: Return the head, which now points to the rearranged list.

Explanation

The algorithm works by separating the odd and even indexed nodes into two separate lists. It then links the tail of the odd list to the head of the even list, effectively merging them into the desired output. The use of pointers allows us to manipulate the list in place without needing to create new nodes or significantly change the structure of the list, thus achieving O(1) extra space complexity. The single iteration through the list results in O(n) time complexity.

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 oddEvenList(head: ListNode | null): ListNode | null {
    if (head === null || head.next === null) {
        return head;
    }

    let odd = head;
    let even = head.next;
    let evenHead = even; // Keep track of the beginning of the even list

    while (even !== null && even.next !== null) {
        odd.next = even.next;
        odd = odd.next;
        even.next = odd.next;
        even = even.next;
    }

    odd.next = evenHead; // Connect the end of the odd list to the beginning of the even list

    return head;
}


// Example usage:
const head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
const reorderedHead = oddEvenList(head);

let output = "";
while(reorderedHead !== null){
    output += reorderedHead.val + " ";
    reorderedHead = reorderedHead.next;
}
console.log(output); // Output: 1 3 5 2 4

const head2 = new ListNode(2, new ListNode(1, new ListNode(3, new ListNode(5, new ListNode(6, new ListNode(4, new ListNode(7)))))));
const reorderedHead2 = oddEvenList(head2);
output = "";
while(reorderedHead2 !== null){
    output += reorderedHead2.val + " ";
    reorderedHead2 = reorderedHead2.next;
}
console.log(output); //Output: 2 3 6 7 1 5 4

Complexity

• Time Complexity: O(n), where n is the number of nodes in the linked list. We iterate through the list once.
• Space Complexity: O(1). We use only a constant number of extra variables.