Problem Statement

Given the head of a singly linked list, group all odd-indexed nodes together followed by even-indexed nodes.

• The node indices are 1-based (first node is index 1 → odd).
• Rearrange the list in-place, without creating new nodes, and return the modified head.

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:

• Number of nodes: 0 ≤ n ≤ 10^4
• Node values: -10^6 ≤ Node.val ≤ 10^6

---

Approach to Solve the Problem (Simple Language)

Idea:

• Maintain two separate pointers:
  • odd → to track the odd-indexed nodes
  • even → to track the even-indexed nodes
• Traverse the list, connecting:
  • odd.next → next odd node
  • even.next → next even node
• Finally, connect the end of odd list to head of even list.

Steps:

1. Handle edge cases: if head is null or head.next is null, return head.
2. Initialize:
   • odd = head
   • even = head.next
   • evenHead = even (to connect at the end)
3. Traverse while even != null && even.next != null:
   • odd.next = even.next → next odd node
   • odd = odd.next
   • even.next = odd.next → next even node
   • even = even.next
4. Connect odd.next = evenHead
5. Return head

Why it works:

• It keeps odd and even nodes in order while reusing existing nodes.
• Time complexity O(n), space O(1).

---

Java Code Solution

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

public class OddEvenLinkedList {

    public static 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;
    }

    public static void printList(ListNode head) {
        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3,
                        new ListNode(4, new ListNode(5)))));
        head = oddEvenList(head);
        printList(head); // Output: 1 3 5 2 4
    }
}

---

Dry Run Example

Input:

head = 1 → 2 → 3 → 4 → 5

Step-by-step Execution:

1. Initialize:
   • odd = 1
   • even = 2
   • evenHead = 2
2. Iteration 1:
   • odd.next = even.next → 3 → odd = 3
   • even.next = odd.next → 4 → even = 4
3. Iteration 2:
   • odd.next = even.next → 5 → odd = 5
   • even.next = odd.next → null → even = null
4. Connect odd.next = evenHead → 2

Final List:

1 → 3 → 5 → 2 → 4

---

Textual Diagram for Understanding

Initial: 1 → 2 → 3 → 4 → 5

Separate odd & even:
Odd nodes: 1 → 3 → 5
Even nodes: 2 → 4

Connect odd to even:
1 → 3 → 5 → 2 → 4

---

Complexity Analysis

• Time Complexity: O(n)
  • Single traversal of linked list
• Space Complexity: O(1)
  • In-place rearrangement, no extra data structures

---

This two-pointer approach efficiently separates odd and even nodes while preserving relative order, using only constant extra space.