Odd Even Linked List

Share

Given the head of a singly linked list, group all odd-indexed nodes together followed by the even-indexed nodes. The first node is odd (index 1), second even (index 2), etc.

Example 1
Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]
Explanation: Odd nodes: 1→3→5, even nodes: 2→4. Join them.
Example 2
Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]

Solution Approach

Use two pointers: odd and even. Link odd.next = even.next, advance odd; link even.next = odd.next, advance even. Finally connect odd tail to even head.

  • Save evenHead = head.next (the start of even list)
  • Weave odd and even pointers alternately
  • Connect odd tail to evenHead
Java
public ListNode oddEvenList(ListNode head) {
    if (head == null) return null;
    ListNode odd = head, even = head.next, 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;
}
Complexity Analysis:

Time complexity: O(n). Single pass
Space complexity: O(1). in-place, no extra space