Logo

Kode$word

LeetCode 328: Odd Even Linked List – Clean and Easy Explanation with Multiple Approaches
LeetCode 328: Odd Even Linked List – Clean and Easy Explanation with Multiple Approaches

LeetCode 328: Odd Even Linked List – Clean and Easy Explanation with Multiple Approaches

Learn How to Rearrange a Linked List by Odd and Even Positions Using Optimal O(1) Space Approach

10 views
0
0
Linked ListPointer ManipulationIn-Place AlgorithmTwo PointersLeetCode Medium
Github icon

Try the Problem

You can practice the problem here:

https://leetcode.com/problems/odd-even-linked-list/


Problem Description (In Very Simple Words)

You are given the head of a linked list.

Your task is:

👉 Rearrange the list such that:

  1. All nodes at odd positions come first
  2. Followed by all nodes at even positions


Important Clarification

❗ This problem is about positions (indices), NOT values.

  1. 1st node → Odd
  2. 2nd node → Even
  3. 3rd node → Odd
  4. 4th node → Even


Example Walkthrough

Example 1

Input:

[1,2,3,4,5]

Positions:

1(odd), 2(even), 3(odd), 4(even), 5(odd)

Output:

[1,3,5,2,4]

Example 2

Input:

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

Output:

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


Constraints

0 <= number of nodes <= 10^4
-10^6 <= Node.val <= 10^6


Core Idea of the Problem

We need to:

  1. Separate nodes into two groups:
  2. Odd index nodes
  3. Even index nodes
  4. Maintain their original order
  5. Finally:
  6. 👉 Attach even list after odd list


Thinking About Different Approaches

When solving this problem, multiple approaches may come to mind:


Approach 1: Create New Lists

Idea

  1. Traverse the list
  2. Create new nodes for odd and even positions
  3. Build two separate lists
  4. Merge them

Problem with This Approach

❌ Uses extra space

❌ Not optimal (violates O(1) space requirement)

❌ Code becomes messy and harder to maintain

Your approach is logically correct, but:

👉 It is not optimal and can be simplified a lot.


Approach 2: Brute Force Using Array/List

Idea

  1. Store nodes in an array
  2. Rearrange based on indices
  3. Rebuild linked list

Complexity

  1. Time: O(n)
  2. Space: O(n) ❌ (Not allowed)


Approach 3: Optimal In-Place Approach (Best Solution)

This is the cleanest and most important approach.


Optimal Approach: Two Pointer Technique (In-Place)

Idea

Instead of creating new nodes:

👉 We rearrange the existing nodes

We maintain:

  1. odd → points to odd nodes
  2. even → points to even nodes
  3. evenHead → stores start of even list

Visualization

Input:

1 → 2 → 3 → 4 → 5

We separate into:

Odd: 1 → 3 → 5
Even: 2 → 4

Final:

1 → 3 → 5 → 2 → 4


Step-by-Step Logic

Step 1: Initialize pointers

odd = head
even = head.next
evenHead = head.next

Step 2: Traverse the list

While:

even != null && even.next != null

Update:

odd.next = odd.next.next
even.next = even.next.next

Move pointers forward:

odd = odd.next
even = even.next

Step 3: Merge

odd.next = evenHead


Clean Java Implementation (Optimal)

class Solution {
public ListNode oddEvenList(ListNode head) {

// Edge case
if(head == null || head.next == null)
return head;

// Initialize pointers
ListNode odd = head;
ListNode even = head.next;
ListNode evenHead = even;

// Rearranging nodes
while(even != null && even.next != null){

odd.next = odd.next.next; // Link next odd
even.next = even.next.next; // Link next even

odd = odd.next;
even = even.next;
}

// Attach even list after odd list
odd.next = evenHead;

return head;
}
}


Dry Run (Important)

Input:

1 → 2 → 3 → 4 → 5

Steps:

Iteration 1:
odd → 1, even → 2
Link:
1 → 3
2 → 4

Iteration 2:
odd → 3, even → 4
Link:
3 → 5
4 → null

Final connection:

5 → 2

Result:

1 → 3 → 5 → 2 → 4


Time Complexity

O(n)

We traverse the list once.


Space Complexity

O(1)

No extra space used.


Why This Approach is Best

FeatureResult
Extra Space❌ None
Clean Code✅ Yes
Efficient✅ O(n)
Interview Friendly✅ Highly


Common Mistakes

❌ Confusing values with positions

❌ Creating new nodes unnecessarily

❌ Forgetting to connect even list at the end

❌ Breaking the list accidentally


Key Learning

This problem teaches:

  1. In-place linked list manipulation
  2. Pointer handling
  3. List partitioning


Final Thoughts

The Odd Even Linked List problem is a classic example of how powerful pointer manipulation can be.

Even though creating new nodes might seem easier at first, the in-place approach is:

👉 Faster

👉 Cleaner

👉 Interview optimized

👉 Tip: Whenever you are asked to rearrange a linked list, always think:

"Can I solve this by just changing pointers instead of creating new nodes?"

That’s the key to mastering linked list problems 🚀

Related Articles

LeetCode 203: Remove Linked List Elements – Step-by-Step Guide for Beginners

LeetCode 203: Remove Linked List Elements – Step-by-Step Guide for Beginners

Learn How to Remove Nodes from a Linked List Using Iteration, Edge Case Handling, and Dummy Node Technique (With Clear Intuition)

Read Article
Reverse Linked List (LeetCode 206) – The One Trick That Changes Everything

Reverse Linked List (LeetCode 206) – The One Trick That Changes Everything

From Confusion to Clarity: Master Linked List Reversal with Intuition, Visualization, and Clean Logic

Read Article
LeetCode 2: Add Two Numbers – Step-by-Step Linked List Addition Explained Clearly

LeetCode 2: Add Two Numbers – Step-by-Step Linked List Addition Explained Clearly

Learn How to Add Numbers Represented as Linked Lists Using Carry Logic, Dummy Nodes, and Iterative Traversal (Beginner Friendly Guide)

Read Article
Remove Nth Node From End – The Smart Way to Solve in One Pass (LeetCode 19)

Remove Nth Node From End – The Smart Way to Solve in One Pass (LeetCode 19)

Stop Counting Twice! Learn the Two-Pointer Trick to Remove Nodes Efficiently from the End of a Linked List

Read Article

Ai Assistant Kas