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 as is.

2. Initialize Pointers: Create pointers odd and even to point to the head of the odd and even sublists respectively. Initialize odd to head and even to head.next. Create a pointer evenHead to keep track of the beginning of the even sublist. This is crucial for connecting the odd and even sublists at the end.

3. Iterate and Relink: Iterate through the list, processing nodes in pairs.

   • The odd pointer always points to the current odd node. Relink its next to the next odd node (skipping one).
   • The even pointer always points to the current even node. Relink its next to the next even node (skipping one).
   • Advance both odd and even pointers accordingly.

4. Concatenate Odd and Even Sublists: After iterating through the entire list, the odd pointer will be at the tail of the odd sublist. Connect the tail of the odd sublist to the head of the even sublist (evenHead).

5. Return the Reordered List: Return the head of the reordered list (which is head, the original odd head).

Explanation

The algorithm efficiently reorders the linked list by cleverly using pointers to traverse and relink nodes. It avoids creating any new nodes, thus satisfying the O(1) extra space constraint. The single pass through the list ensures the O(n) time complexity. The key is understanding how to manage the odd and even pointers to build the rearranged list. The use of evenHead ensures the even sublist is correctly appended to the end.

Code (C#)

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public ListNode OddEvenList(ListNode head) {
        if (head == null || head.next == null) return head;

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

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

        odd.next = evenHead; // Connect odd list tail to even list head

        return head;
    }
}

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 to maintain pointers.