MediumLinked List

Odd Even Linked List

1 approach, code in every language

Given the head of a singly linked list, reorder it so that every node sitting at an odd position comes before every node sitting at an even position. Positions are counted starting from 1, based on where the nodes currently sit, not on their values.

Within the odd group and within the even group the original relative order must be preserved. The rearrangement has to run in O(1) extra space and O(n) time.

Example 1

Input: head = [1,2,3,4,5]

Output: [1,3,5,2,4]

Odd-position nodes 1, 3, 5 are chained first, then the even-position nodes 2 and 4 follow.

Example 2

Input: head = [2,1,3,5,6,4,7]

Output: [2,3,6,7,1,5,4]

Positions 1,3,5,7 hold 2,3,6,7 and positions 2,4,6 hold 1,5,4; the odd group leads and the even group trails.

Constraints

The number of nodes is in the range [0, 10^4].
-10^6 <= Node.val <= 10^6

Two Chains, Then Splice

Weave two separate chains for odd and even positions, then join them end to end.

Loading animation…

Intuition

Rather than shuffling values, we rewire the links so odd-position nodes form one chain and even-position nodes form another. We keep an odd pointer and an even pointer, plus a saved reference to the first even node so we can attach the even chain later. Walking forward, each pointer skips over its neighbor of the other parity, effectively splitting the list into two interleaved strands. When we run out of nodes, we simply connect the tail of the odd chain to the head of the even chain. Only a handful of pointers are used, so the space stays constant.

Algorithm walkthrough

1If the list is empty, return it as is; otherwise set odd to head and even to head.next.
2Remember evenHead, the first even-position node, so it can be reattached later.
3While even and even.next exist, link odd.next to even.next and advance odd, then link even.next to odd.next and advance even.
4This threads odd-position nodes together and even-position nodes together in order.
5Finally set odd.next to evenHead so the even chain follows the odd chain, and return head.

Implementation

class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            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

Time

O(n)

Space

O(1)

Each node is visited once and only pointers are rewired, so no extra memory grows with n.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Linked List

After the pattern

Now solve one you haven't seen.

Regroup the Bucket Line is our own problem on the technique behind Odd Even Linked List: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free