LC328 Odd Even Linked List 🟡

👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ

Relink in place — split into odd and even chains, then join odd’s tail to even’s head.

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

The first node is considered odd, and the second node is even, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

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 (ข้อจำกัด)

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

Full solution · Try yourself firstพับไว้ด้านใน — คลิกเมื่อพร้อมดู

This matches the "stitching (Merge)" signal — but here we split the same list into two chains, then join them back, without allocating new nodes (Space O(1)).

1. Mindset Shift

The naive way is to collect odd-index values in one list and even-index values in another, then concatenate — but that uses Space O(n) and breaks the constraint!

Key insight: don’t build new nodes — use two pointers odd and even to rewire next links, forming two sub-chains, then attach the odd chain’s tail to the even chain’s head.

2. The Logic — 4 Steps

Open two chains, then stitch until done:

Edge case — empty or single node → return head
Prep chains — odd at first · even at second · even_head remembers the even head (critical!)
Stitch — while even and even.next: odd jumps to the next odd, then even jumps to the next even
Join — odd.next = even_head, then return head

3. LeetCode-Ready Code

Turn the two-chain rules into code:

Submit this on LeetCodepython

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Step 1: 0 or 1 node — nothing to do
        if head is None or head.next is None:
            return head

        odd = head                  # odd-position pointer
        even = head.next            # even-position pointer
        even_head = even            # remember even head for the final join

        # Step 3: stitch until even runs out
        while even and even.next:
            odd.next = even.next    # odd jumps to next odd
            odd = odd.next
            even.next = odd.next    # even jumps to next even
            even = even.next

        # Step 4: join odd tail to even head
        odd.next = even_head
        return head

4. Dry Run — 1 → 2 → 3 → 4 → 5

even_head is saved at value 2 from the start

Step	odd (val)	even (val)	Note	list now
Before loop	1	2	not stitched yet	1 → 2 → 3 → 4 → 5
Round 1	3	4	odd → 3 · even → 4	odd: 1 → 3 → 4 → 5 \| even: 2 → 4 → 5
Round 2	5	None	odd → 5 · even done → stop	odd: 1 → 3 → 5 \| even: 2 → 4
After loop	5	—	odd.next = even_head	1 → 3 → 5 → 2 → 4

The | mark splits two pieces: left = odd chain so far · right = even chain so far — final train [1, 3, 5, 2, 4]

5. Edge Cases & Pitfalls

The "forgot even_head" case — the #1 mistake on this problem:

During the loop the even pointer keeps moving forward
If you didn’t save the head earlier, you won’t know where the odd tail should attach

The four lines inside the loop can’t be reordered

You must advance odd first before reading odd.next for the next even — swap the order and the links point at the wrong nodes!

6. Time & Space Complexity

Time O(n) — one pass through every node
Space O(1) — only rewiring links, no new list

💡 Pattern summary

Splitting one list into several chains by rewiring next pointers in place, then joining them back, is a very space-cheap pattern — the key is always remembering the head of any chain you’ll attach later.