Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

Problem gist

Given a singly linked list, rearrange its existing nodes so that every node in an odd-numbered position comes first, followed by every node in an even-numbered position. The relative order inside each group must stay unchanged.

For example, 1 → 2 → 3 → 4 → 5 becomes 1 → 3 → 5 → 2 → 4. Here, “odd” and “even” describe one-based positions, not node values: the first, third, and fifth nodes form the odd group even if their values happen to be even.

The list must be reorganized in O(n) time with O(1) auxiliary space, so copying all nodes into arrays or separate lists is unnecessary. The optimal approach builds the two position groups in place and joins them at the end.

Deriving the optimal solution

Imagine separating the original links into two chains while walking through the list:

  • The odd chain starts at the first node and should receive the third, fifth, seventh, and later odd-positioned nodes.
  • The even chain starts at the second node and should receive the fourth, sixth, eighth, and later even-positioned nodes.

Keep a tail pointer for each chain. The node after the even tail is always the next odd-positioned node, so link the odd tail to it and advance the odd tail. The node after that new odd tail is the next even-positioned node, so link the even tail to it and advance the even tail. Repeating these two rewires consumes one odd-even pair per iteration.

The original second node must also be saved as even_head. Without that reference, advancing the even tail would lose the beginning of the even chain. After no complete pair remains, connect the odd tail to even_head.

For 1 → 2 → 3 → 4 → 5, the pointers produce these chains:

  1. Start with odd chain 1 and even chain 2.
  2. Append 3 to the odd chain and 4 to the even chain.
  3. Append 5 to the odd chain; there is no later even node.
  4. Connect the odd tail 5 to the saved even head 2.

Each iteration preserves the original order within both chains because nodes are appended in the same order in which they appear. Every node is visited a constant number of times, giving O(n) time. Only three persistent node references are needed, so the auxiliary space is O(1). Since the output may require changing links across the whole list, the linear running time is asymptotically optimal.

Python solution

from __future__ import annotations


# LeetCode provides this class:
# class ListNode:
#     def __init__(self, value: int = 0, next_node: ListNode | None = None):
#         self.val = value
#         self.next = next_node


class OddEvenLinkedListReorderer:
    """Group nodes by one-based position while preserving group order."""

    @staticmethod
    def reorder(head: ListNode | None) -> ListNode | None:
        """Rewire the list in place and return its original head."""
        if head is None or head.next is None:
            return head

        odd_tail = head
        even_head = head.next
        even_tail = even_head

        # At the start of each iteration, even_tail.next is the next node
        # belonging to the odd-positioned chain.
        while even_tail is not None and even_tail.next is not None:
            next_odd_node = even_tail.next
            next_even_node = next_odd_node.next

            odd_tail.next = next_odd_node
            odd_tail = next_odd_node

            # This also terminates the even chain when the list length is odd.
            even_tail.next = next_even_node
            even_tail = next_even_node

        # Append the complete even-positioned chain after the odd chain.
        odd_tail.next = even_head
        return head


class Solution:
    """LeetCode-compatible entry point."""

    def oddEvenList(self, head: ListNode | None) -> ListNode | None:
        return OddEvenLinkedListReorderer.reorder(head)

Interview follow-ups

Why does the algorithm preserve relative order within both groups?

The traversal discovers odd-positioned nodes in the order 1, 3, 5, ... and even-positioned nodes in the order 2, 4, 6, .... Each discovered node is appended to its group’s current tail, and no node is inserted before another node that was discovered earlier. The two chains are therefore stable partitions of the original list. Joining the odd tail to the saved even head changes only the boundary between groups, not either group’s internal order.

What changes if odd and even refer to node values instead of positions?

The next destination could no longer be inferred from position. Traverse the list once, detach each node, and append it to either an odd-value chain or an even-value chain according to node.val % 2. Keep head and tail references for both chains, then join the requested first chain to the second.

This is still a stable in-place partition with O(n) time and O(1) auxiliary space. The extra care is structural: each node should be detached before being appended, and the final tail must point to None, or an obsolete original link could create an incorrect suffix or a cycle.

How would the solution generalize to grouping positions by their remainder modulo k?

Maintain a head and tail for each of the k remainder groups. As the list is traversed, detach each node and append it to the group selected by its one-based position modulo k. Finally, connect the nonempty groups in the requested remainder order.

The traversal and concatenation take O(n + k) time and the group references take O(k) extra space. When k is a fixed constant, the auxiliary space is effectively constant; when k is part of the input, it must be reported as O(k). The same append-only invariant preserves order inside every group.

What if the original list must remain unchanged?

An in-place relinking algorithm cannot simultaneously preserve the original list’s links. Instead, traverse the original nodes, copy the odd-positioned values into one new chain and the even-positioned values into another, then connect the copies. If the new list must share the original node objects, the API would need a non-link representation such as an array of node references because one next field cannot encode both orders.

Copying produces the same stable ordering in O(n) time, but it requires O(n) additional space for the new nodes. That memory cost is unavoidable when two independently linked versions must coexist.

How should production code handle an input list that may contain a cycle?

The LeetCode contract guarantees an acyclic list, but an untrusted API can first run Floyd’s slow-and-fast pointer algorithm. If the pointers meet, reject the input or return a validation error before attempting the rearrangement. Otherwise, proceed normally.

Cycle validation takes O(n) time and O(1) space, so it does not change the asymptotic bounds. It does add a full pass, but it prevents the reordering loop from running forever or corrupting a cyclic structure in a way that is difficult for callers to diagnose.

Can the grouping be written recursively?

A recursive traversal can classify nodes while the calls advance through the list, but the cleanest stable version still needs references to the odd and even tails. More importantly, recursion consumes O(n) call-stack space and can exceed Python’s recursion limit on a long input.

The iterative solution expresses the same invariant directly, keeps the required O(1) auxiliary-space bound, and avoids stack-overflow risk. Recursion offers no time-complexity advantage because every node must still be processed once.