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:

• The relative order inside both the even and odd 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. Initialization: We need pointers to track the odd and even sublists. Let's call them odd and even, and their tails oddTail and evenTail. We'll also need a pointer to iterate through the list, current.

2. Iteration: We iterate through the linked list. For each node:

   • If the node's index is odd, we append it to the odd list (or set odd to the node if it's the first odd node). Update oddTail.
   • If the node's index is even, we append it to the even list (or set even to the node if it's the first even node). Update evenTail.

3. Concatenation: After iterating, we connect the tail of the odd list to the head of the even list.

4. Return: Return the head of the odd list.

Explanation:

The algorithm efficiently separates the odd and even nodes by maintaining separate pointers for each group. The use of oddTail and evenTail ensures constant-time appending to the ends of the sublists. The final concatenation step combines the two sublists to produce the reordered list. The space complexity is O(1) because we are not using any extra data structures proportional to the input size. The time complexity is O(n) because we iterate through the list once.

Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) return head; //Handle empty or single-node lists

        ListNode odd = head;          //Head of odd list
        ListNode even = head.next;     //Head of even list
        ListNode oddTail = odd;       //Tail of odd list
        ListNode evenTail = even;     //Tail of even list
        ListNode current = even.next; //Iterator starting from the third node
        boolean oddTurn = false;     //Indicates whether to append to odd or even list


        while (current != null) {
            if (oddTurn) { // Append to odd list
                oddTail.next = current;
                oddTail = oddTail.next;
            } else { // Append to even list
                evenTail.next = current;
                evenTail = evenTail.next;
            }
            current = current.next;
            oddTurn = !oddTurn;
        }

        oddTail.next = even; //Connect the tail of odd list to the head of even list
        evenTail.next = null; //Ensure the even list ends properly

        return odd;
    }
}

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 a constant number of pointers regardless of the input size.