Course4all
Join us on telegram
Home/dsa/Linked List Patterns/Odd Even Linked List

Odd Even Linked List

Master this topic with zero to advance depth.

Odd Even Linked List

Group nodes with odd indices together followed by even indices.

Visual Representation

1 -> 2 -> 3 -> 4 -> 5 Odd: 1 -> 3 -> 5 Even: 2 -> 4 Result: 1 -> 3 -> 5 -> 2 -> 4
Medium

Examples

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

Level I: Brute Force (Two Lists/Arrays)

Intuition

Traverse the list and store odd-indexed nodes in one list/array and even-indexed nodes in another. Then, link the end of the odd list to the head of the even list.

⏱ O(N)💾 O(N)

Detailed Dry Run

1->2->3->4. Odd: [1, 3]. Even: [2, 4]. Result: 1->3->2->4.

java
public ListNode oddEvenList(ListNode head) {
    if (head == null) return null;
    List<ListNode> odds = new ArrayList<>(), evens = new ArrayList<>();
    ListNode curr = head; int i = 1;
    while (curr != null) {
        if (i % 2 != 0) odds.add(curr);
        else evens.add(curr);
        curr = curr.next; i++;
    }
    for (int j = 0; j < odds.size() - 1; j++) odds.get(j).next = odds.get(j+1);
    for (int j = 0; j < evens.size() - 1; j++) evens.get(j).next = evens.get(j+1);
    if (!evens.isEmpty()) evens.get(evens.size() - 1).next = null;
    if (!odds.isEmpty()) odds.get(odds.size() - 1).next = evens.isEmpty() ? null : evens.get(0);
    return odds.get(0);
}
Approach 2

Level III: Two Pointers (In-place)

Intuition

Maintain odd and even pointers, cross-linking as you traverse.

⏱ O(N)💾 O(1)
java
public ListNode oddEvenList(ListNode head) {
    if (head == null) return null;
    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;
}
← Previous QuestionRemove Linked List Elements
Next Question →Swap Nodes in Pairs