Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        odd = head
        even = head.next
        even_head = even

        while even and even.next:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next

        odd.next = even_head
        return head
      

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* odd = head;
        ListNode* even = head->next;
        ListNode* evenHead = even;

        while (even && even->next) {
            odd->next = even->next;
            odd = odd->next;
            even->next = odd->next;
            even = even->next;
        }
        odd->next = evenHead;
        return head;
    }
};
      

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
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;

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

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var oddEvenList = function(head) {
    if (!head || !head.next) return head;
    let odd = head;
    let even = head.next;
    let evenHead = even;

    while (even && even.next) {
        odd.next = even.next;
        odd = odd.next;
        even.next = odd.next;
        even = even.next;
    }
    odd.next = evenHead;
    return head;
};
      

Problem Description

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.

• Input: The input is a singly linked list with nodes having values and next pointers.
• Output: Return the head of the modified list where all odd-indexed nodes are grouped first, followed by the even-indexed nodes. The relative order within the odd and even groups should be preserved.
• Constraints:
  • Do not create new nodes; rearrange the existing nodes by changing their next pointers.
  • The solution must use O(1) extra space and O(n) time, where n is the number of nodes in the list.
  • There is only one valid way to reorder the list for each input.

Thought Process

At first glance, it might seem that we need to create two new lists: one for odd-indexed nodes and one for even-indexed nodes, then combine them. However, the problem restricts us from creating new nodes or using extra space proportional to the input size.

The key is to rearrange the next pointers of the existing nodes in-place. We need to traverse the list and separate the nodes into two sequences: one for odd positions and one for even positions. After we've separated them, we simply attach the end of the odd sequence to the head of the even sequence.

This approach avoids the brute-force method of copying nodes or using arrays, and instead leverages pointer manipulation for efficiency.

Solution Approach

Let's break down the steps of the algorithm:

1. Edge Case Check: If the list is empty or has only one node, return it as-is.
2. Initialize Pointers:
   • Let odd point to the first node (head).
   • Let even point to the second node (head.next).
   • Save the head of the even list (even_head), as we will need to attach the odd list's end to this later.
3. Rearrange Nodes:
   • Iterate as long as even and even.next are not null.
   • Set odd.next to even.next (the next odd node), and move odd forward.
   • Set even.next to odd.next (the next even node), and move even forward.
4. Combine Lists:
   • After the loop, attach odd.next to even_head to link the odd and even sequences.
5. Return Result:
   • Return the original head, which now points to the rearranged list.

This method maintains the original ordering within the odd and even groups and uses only a constant number of pointers, satisfying the space and time requirements.

Example Walkthrough

Let's use the input list: 1 -> 2 -> 3 -> 4 -> 5

1. Initial pointers:
   • odd = 1
   • even = 2
   • even_head = 2
2. First iteration:
   • odd.next = even.next = 3
   • odd = 3
   • even.next = odd.next = 4
   • even = 4

   List now: 1 -> 3 -> 4 -> 5 (but 2 and 4 still accessible via even_head)

3. Second iteration:
   • odd.next = even.next = 5
   • odd = 5
   • even.next = odd.next = null
   • even = null

   List now: 1 -> 3 -> 5 (odds), 2 -> 4 (evens via even_head)

4. Final step:
   • odd.next = even_head (2)

   Final list: 1 -> 3 -> 5 -> 2 -> 4

The nodes at odd indices are grouped first, followed by the nodes at even indices, preserving their original order within each group.

Time and Space Complexity

• Brute-force Approach:
  • If we used arrays or lists to store odd and even nodes, then rebuilt the linked list, the time complexity would still be O(n), but the space complexity would be O(n) due to the use of extra storage.
• Optimized In-place Approach:
  • Time Complexity: O(n), because we traverse the list at most once, visiting each node exactly once.
  • Space Complexity: O(1), as we only use a fixed number of pointers regardless of input size.

Summary

The Odd Even Linked List problem demonstrates the power of pointer manipulation in linked lists. By carefully separating nodes into odd and even indexed groups using only a few pointers, we achieve the required grouping in a single pass and with constant extra space. This solution is both efficient and elegant, making full use of the properties of linked lists and avoiding unnecessary data structures or memory allocation.