The O(n) Club: Odd Even Linked List: When Indices, Not Values, Go Rogue

The O(n) Club: Odd Even Linked List — When Indices, Not Values, Go Rogue

⚡ TL;DR

Don’t confuse “odd” with funky node values: This is about putting odd-positioned nodes before even-positioned ones in one smooth, in-place list. Here’s your caffeine-fueled starter Java one-liner:

// Java quickie (assume ListNode has int val, ListNode next)
public ListNode oddEvenList(ListNode head) {
  if (head == null || head.next == null) return head;
  ListNode odd = head, even = head.next, evenHead = even;
  while (even != null && even.next != null) {
    odd.next = even.next; odd = odd.next;
    even.next = odd.next; even = even.next;
  }
  odd.next = evenHead; return head;
}

🧠 How Devs Usually Mess This Up

Let’s roast some classics:
1. Value, not position: Grouping by node value (odd/even) gets you zero points. Sorry.
2. Extra space sins: Copying nodes into arrays or new lists—nope, in-place only.
3. Order who? Scrambling node order inside groups is a sure-fire way to fail the test cases. Hold the chaos.

🔍 What’s Actually Going On

Imagine a robot bouncer at a VIP tech meetup: Your odd-indexed guests form one line, the evens another. Nobody swaps places, nobody gets kicked out. You have two stamps (“odd”, “even”) and one shiny linked list. Instead of creating two lists for each stamp, you use two pointers, swapping their .next with the elegance of a seasoned Java barista. When the dust settles, you just stick the lines together—no one notices a thing except the memory profiler (who is extremely proud).

🛠️ PseudoCode

• Check if the list is empty or one lonely node. Do nothing.
• Point odd to head, even to head.next. Store even head.
• While even and even.next aren’t null:
  

  // In Java:
  odd.next = even.next; odd = odd.next;
  even.next = odd.next; even = even.next;

• After loop, jam even list after odd’s tail:
  

  odd.next = evenHead;

• Return the (still intact!) head pointer.

💻 The Code

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
 public class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode odd = head, even = head.next, evenHead = even;
        while (even != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Null or single item? Don’t touch, just return.
• Don’t mix up values for positions: 1st, 2nd, not 1, 2!
• Changing the sequence inside odds/evens: no shuffling allowed.
• No extra lists—this dance is strictly pointer-only.
• Lose track of evenHead, lose half your list.
• Runtime? O(n) because each node gets one handshake. Space? O(1) pointer juggling.

🧠 Interviewer Brain-Tattoo

“Odd and even means positions. Memorize that, or the only thing split will be your resume and the short list!”