DSA sheet · Linked List · Basic operations pattern

Odd Even Linked List

The last question of the basic-operations pattern. We rearrange a list so that all nodes at odd positions come first and all nodes at even positions come after them. The teacher starts with an array-based brute force, then builds the optimal answer: split the list into two chains in place with two pointers, then join the chains. It is a great exercise in rewiring .next without losing any node, and in finding the exact loop condition for odd and even lengths.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

Part 0 · Before starting

What is a linked list node?

A linked list is a chain of nodes. Each node holds a value (val) and a link to the next node (next). The last node's next is None.

given by LeetCode, don't write this in the solution
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val      # the number stored in this node
        self.next = next    # the next node, or None at the end
[1] → [2] → [3] → [4] → [5] → None
 ↑
head

Positions, not values

Position 1 is the head, position 2 is the next node, and so on. "Odd nodes" means the nodes at positions 1, 3, 5, …; "even nodes" means positions 2, 4, 6, …. The values inside don't matter at all.

Part A · Brute force with an array

LeetCode 328 · Odd Even Linked List

1The question in simple words

Given the head of a list, rearrange it so that the nodes at odd positions come first (keeping their order), followed by the nodes at even positions (keeping their order). Return the head of the result.

Example 1
input:  [1] → [2] → [3] → [4] → [5] → None
output: [1] → [3] → [5] → [2] → [4] → None
         └── odd ───────┘  └ even ┘
Example 2: values don't matter
input:  [0] → [3] → [5] → [1] → [4] → None
output: [0] → [5] → [4] → [3] → [1] → None

In example 1, 1 links to 3, 3 links to 5, and after 5 (the end of the odd group) comes the first even node, 2, then 4. In example 2, the teacher swaps in different values to show that we pick nodes by position: positions 1, 3, 5 hold 0, 5, 4 and positions 2, 4 hold 3, 1.

2What the constraints tell us

3Intuition: copy out, sort into two piles, rebuild

Arrays have indices; linked lists don't. So the simplest first idea: copy every value into an array, where positions are easy to see. Then deal the values into two piles (odd positions, even positions), build a new list for each pile, and join the end of the first pile to the start of the second.

4Building the logic from the example

array:   index  0   1   2   3   4
         value  1   2   3   4   5
position         1   2   3   4   5
Doubt: index 0 is "even" in the array, but the question calls that node "odd". Which is it?
→ Both, depending on how you count. Arrays count from 0, list positions count from 1, so they are always off by one. Array index 0, 2, 4 (even indices) are list positions 1, 3, 5 (odd positions). Just remember: even array index = odd list position. The teacher points out exactly this mix-up.

5Approach steps

  1. If the list is empty, return it.
  2. Walk the list and copy all values into an array.
  3. For each index i: create a new node; put it on the "odd" chain if i is even, otherwise on the "even" chain. Keep a head and a tail for each chain.
  4. Link the odd chain's tail to the even chain's head.
  5. Return the odd chain's head.

6Code (Python)

Odd Even List, brute force (extra array + new nodes)
class Solution:
    def oddEvenList(self, head):
        if head is None:
            return head

        vals = []                         # 1) copy values into an array
        curr = head
        while curr:
            vals.append(curr.val)
            curr = curr.next

        odd_head = odd_tail = None        # 2) build two new chains
        even_head = even_tail = None
        for i, v in enumerate(vals):
            node = ListNode(v)
            if i % 2 == 0:                # index 0, 2, 4 = positions 1, 3, 5
                if odd_head is None:
                    odd_head = odd_tail = node
                else:
                    odd_tail.next = node
                    odd_tail = node
            else:                         # index 1, 3 = positions 2, 4
                if even_head is None:
                    even_head = even_tail = node
                else:
                    even_tail.next = node
                    even_tail = node

        odd_tail.next = even_head         # 3) odd chain, then even chain
        return odd_head

7Code line by line

linewhat it means
if head is None: return head0 nodes is allowed: nothing to rearrange.
while curr: vals.append(curr.val)Copy every value into a Python list, so we get indices.
odd_head = odd_tail = NoneEach new chain needs a head (to remember where it starts) and a tail (to add the next node in O(1)).
if i % 2 == 0:Even array index = odd list position.
if odd_head is None: odd_head = odd_tail = nodeThe first node of a chain is both its head and its tail.
odd_tail.next = node odd_tail = nodeHang the new node after the tail, then the new node becomes the tail.
odd_tail.next = even_headJoin: the end of the odd chain points to the start of the even chain. (If there's only one node, even_head is None, which is exactly right.)

8Dry run on 1 → 2 → 3 → 4 → 5

ivaluepileodd chaineven chain
01odd1—
12even12
23odd1 → 32
34even1 → 32 → 4
45odd1 → 3 → 52 → 4
join1 → 3 → 5 → 2 → 4 → None

9Complexity & remember

Remember the brute force Array gives you indices → deal into two piles → join odd tail to even head. Works, but O(n) array + O(n) new nodes. The fix: rearrange the existing nodes.

Part B · Optimal: two chains in place

1The question (same as Part A)

Same rearrangement, but now with O(1) extra space: no array, no new nodes. We only change .next links of the nodes we already have.

2What the constraints tell us

3Intuition: unzip the list into two chains

Think of the list as a zipper with teeth from two sides: odd, even, odd, even… We pull it apart into two chains, odd nodes linked to each other and even nodes linked to each other, and finally hang the even chain after the odd chain.

4Building the logic from the example

First try: odd.next = odd.next.next, and why we need the even pointer

We want 1 to link to 3. 3 is odd.next.next, so the first idea is odd.next = odd.next.next. That does link 1 to 3, but now nobody points to 2. Node 2 is lost forever, and we needed it for the even chain. So before rewiring, we keep a pointer on 2: even = head.next. That's the "save next before changing a pointer" rule in action.

Setup: odd = head (node 1), even = head.next (node 2), even_head = even (stays on node 2 forever).

The four moves, found one at a time

[1] → [2] → [3] → [4] → [5] → None
 ↑     ↑
odd   even, even_head
  1. Link odd to the next odd node. The next odd node (3) is right after even, so: odd.next = even.next. Now 1 → 3. Node 2 isn't lost, because even still holds it, and 2 still points to 3.
  2. Move odd forward. We're done with node 1, there's no reason to wait there. odd = odd.next. Because we already changed 1's next to 3, this moves odd to 3, not to 2.
  3. Link even to the next even node. The next even node (4) is right after the new odd: even.next = odd.next. Now 2 → 4.
  4. Move even forward. even = even.next, so even is on 4.
after one round (odd is on [3], even is on [4]):
links now:   1 → 3,   2 → 4,   3 → 4 (not changed yet),   4 → 5
odd chain:   [1] → [3]
even chain:  [2] → [4] → [5] → None
              ↑     ↑
      even_head     even

Repeat: 3 should link to 5, which is even.next. That is the same line as before, odd.next = even.next! The four moves repeat exactly, so they go in a loop.

When do we stop? Two cases

Odd length (1 2 3 4 5): second round: 3 → 5, odd = 5, 4 → 5.next = None, even = None. There are no nodes left to place. even became None, that's the stop signal.

Even length (1 2 3 4): after the first round, odd is on 3 and even is on 4. 1 → 3 and 2 → 4 are done. Does 3 need to link to another odd node? No, there isn't one. Does 4? No. So we stop, but even isn't None, it's on node 4. The signal here is even.next is None.

So: stop if even is None or even.next is None. Turned around for the while: keep going while even is not None and even.next is not None.

Doubt 1: why and, and why check even first?
→ We need both to be true to continue. And the order matters: if even is None, Python's and stops right there and never evaluates even.next. If we wrote even.next first, or used or (which goes on to check the second part when the first is false), we'd read "next of None" → crash. The teacher first said "or" while speaking and then corrected it to "and" for this reason.
Doubt 2: why is the condition about even and not odd?
→ The even pointer is always one step ahead of the odd pointer in the original order, so it reaches the end first. Each round needs even.next (the next odd node) to exist; if it does, odd.next after moving is safe to read as well.

After the loop: join the two chains

Can we return head right after the loop? Check with 1 2 3 4. After the loop the links are 1 → 3, 2 → 4, and 3 → 4 (never changed). Walking from head gives 1 → 3 → 4, so node 2 is missing. We must link the last odd node to the first even node: odd.next = even_head. That's why we saved even_head at the start: even itself has moved away from node 2.

Result: 1 → 3 → 2 → 4 → None. ✓ And the even chain already ends in None (the last even node's next was set to odd.next, or it was the real tail), so nothing loops.

5Approach steps

  1. If head is None or head.next is None → return head.
  2. odd = head, even = head.next, even_head = even.
  3. While even and even.next exist: odd.next = even.next; odd = odd.next; even.next = odd.next; even = even.next.
  4. Join: odd.next = even_head.
  5. Return head (node 1 is still first).

6Code (Python)

Odd Even List, optimal (in place)
class Solution:
    def oddEvenList(self, head):
        if head is None or head.next is None:   # 0 or 1 node
            return head

        odd = head
        even = head.next
        even_head = even                 # remember where the even chain starts

        while even is not None and even.next is not None:
            odd.next = even.next         # odd skips over even
            odd = odd.next
            even.next = odd.next         # even skips over the new odd
            even = even.next

        odd.next = even_head             # odd chain, then even chain
        return head

7Code line by line

linewhat it means
if head is None or head.next is None: return head0 or 1 node: already "rearranged". Also protects head.next below.
odd = head even = head.nextTwo walkers: one on the first odd node, one on the first even node. even also saves node 2 so it isn't lost when 1 skips over it.
even_head = evenA pointer that never moves: we need the first even node for the final join.
while even is not None and even.next is not None:Stop when even is None (odd length) or is the last node (even length). and + this order avoids reading None.next.
odd.next = even.nextRewire: the current odd node now points to the next odd node.
odd = odd.nextMove to that next odd node.
even.next = odd.nextRewire: the current even node points to the next even node (or None).
even = even.nextMove to that next even node (or None).
odd.next = even_headHang the even chain after the last odd node.
return headThe head (node 1) never changed position.

8Dry run

Odd length: 1 → 2 → 3 → 4 → 5 (even_head = [2] the whole time)

steppointerswhat changeschains after this step
0odd=[1], even=[2]setup1→2→3→4→5
1check: even=[2], even.next=[3] ✓1.next = [3]; odd=[3]odd: 1→3 even: 2→3
22.next = [4]; even=[4]odd: 1→3 even: 2→4
3check: even=[4], even.next=[5] ✓3.next = [5]; odd=[5]odd: 1→3→5 even: 2→4→5
44.next = None; even=Noneodd: 1→3→5 even: 2→4
5check: even is None → stop5.next = even_head [2]1→3→5→2→4→None ✓

Snapshots:

start:          [1] → [2] → [3] → [4] → [5] → None
                 odd   even

after round 1:  [1] → [3] → [4] → [5] → None        odd = [3]
                [2] → [4]   (2 skips 3)              even = [4]

after round 2:  [1] → [3] → [5] → None               odd = [5]
                [2] → [4] → None                     even = None

after the join: [1] → [3] → [5] → [2] → [4] → None

Even length: 1 → 2 → 3 → 4

steppointerswhat changeschains after this step
0odd=[1], even=[2]setup1→2→3→4
1even=[2], even.next=[3] ✓1.next=[3], odd=[3], 2.next=[4], even=[4]odd: 1→3→4 even: 2→4
2even=[4], even.next=None → stop3.next = even_head [2]1→3→2→4→None ✓

Without the join, walking from head would give 1 → 3 → 4 (node 2 missing), which is why even_head exists.

9Complexity & remember

Remember Odd Even odd=head, even=head.next, even_head=even · loop while even and even.next: odd.next=even.next, odd=odd.next, even.next=odd.next, even=even.next · then odd.next = even_head.

Part C · Revision page

Brute force (array)Optimal (two chains)
ideacopy values out, rebuild two new lists, joinrewire the existing nodes into two chains, join
new nodes?yes, n of themno
timeO(n)O(n)
extra spaceO(2n): array + new nodesO(1)
key detaileven array index = odd positionsave even_head; loop while even and even.next
lengthwhat stops the loopwhere odd ends
odd (1 2 3 4 5)even becomes Nonelast node (5)
even (1 2 3 4)even.next is Nonesecond-last node (3)
If you remember only 5 lines 1. Group by position, not value.
2. Two walkers: odd on 1, even on 2, plus even_head that never moves.
3. Each round: odd skips even, move odd; even skips odd, move even.
4. while even and even.next: covers odd and even lengths, and avoids None.next.
5. Finish with odd.next = even_head, return head. O(n) time, O(1) space.
Mistakes to avoid ✗ grouping by odd/even values
✗ odd.next = odd.next.next without a pointer on the even node (it's lost)
✗ forgetting even_head, or using even for the join (it has moved)
✗ or instead of and in the loop, or checking even.next before even
✗ missing the 0 / 1 node base case (head.next on None)
test it yourself (paste under either solution above)
class ListNode:
    def __init__(self, val=0, next=None):
        self.val, self.next = val, next

def build(vals):
    head = None
    for v in reversed(vals):
        head = ListNode(v, head)
    return head

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

s = Solution()
print(to_list(s.oddEvenList(build([1, 2, 3, 4, 5]))))   # [1, 3, 5, 2, 4]
print(to_list(s.oddEvenList(build([1, 2, 3, 4]))))      # [1, 3, 2, 4]
print(to_list(s.oddEvenList(build([0, 3, 5, 1, 4]))))   # [0, 5, 4, 3, 1]
print(to_list(s.oddEvenList(build([]))))                # []

Based on this video: Odd Even Linked List