Odd Even Linked List

Problem Statement

When dealing with a singly linked list given by the head pointer, the task is to rearrange all nodes such that all nodes located at odd indices in the list are grouped together, followed by those at even indices. It's essential to note:

• The index of the first node starts at 1, making it "odd," while the second node is "even," and the pattern continues alternately.
• The nodes must retain their original relative ordering within their respective odd and even groups after grouping.
• The solution must adhere to O(1) extra space usage and O(n) time complexity, ensuring efficiency in both space and processing time for potentially long linked lists.

Examples

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]

Constraints

• The number of nodes in the linked list is in the range [0, 104].
• -106 <= Node.val <= 106

Approach and Intuition

To tackle this problem of group nodes into odd and even indexed sets, we can employ a two-pointer technique:

1. Initialize two pointers: odd to start on the first node (head of the linked list), and even to start on the second node.
2. Additionally, maintain a pointer evenHead that keeps a reference to the start of the even-index nodes.
3. Traverse the linked list while adjusting the pointers:
   • Move the odd pointer through the list by jumping to the node two steps ahead (skipping the even indexed node).
   • Likewise, advance the even pointer by skipping over the next node, which will be odd indexed.
4. This leapfrogging continues until either the odd or even pointer runs out of nodes to jump to (i.e., when they encounter the end of the list or a null node).
5. Finally, connect the last node in the odd-indexed group (where odd.next would be null) to the evenHead, which marks the start of even-indexed nodes.

By the end of this process, all nodes that originally had odd indices will be grouped together at the beginning of the list followed by all nodes with even indices, all while maintaining their original order in their respective groups. The completion of these steps achieves the desired arrangement of the linked list in linear time and constant space, fulfilling the problem constraints and requirements efficiently.

Solutions

public class Solution {
    public ListNode rearrangeNodes(ListNode head) {
        if (head == null) return null;
        ListNode oddNode = head, evenNode = head.next, startEvenNode = evenNode;
        while (evenNode != null && evenNode.next != null) {
            oddNode.next = evenNode.next;
            oddNode = oddNode.next;
            evenNode.next = oddNode.next;
            evenNode = evenNode.next;
        }
        oddNode.next = startEvenNode;
        return head;
    }
}