# Odd Even Linked List
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/odd-even-linked-list)
Canonical: https://scaleengineer.com/dsa/problems/odd-even-linked-list
**Data structures:** Linked List
---
## Problem
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:**

![](https://assets.glich.co/dsa/odd-even-linked-list/image0.jpg) 

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

**Example 2:**

![](https://assets.glich.co/dsa/odd-even-linked-list/image1.jpg) 

**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, 104]`.
* `-106 <= Node.val <= 106`

# Approaches
## Separate Lists using Dummy Nodes
A straightforward way to solve this problem is to conceptually split the original list into two separate lists: one containing all the odd-indexed nodes and another containing all the even-indexed nodes. We can achieve this by iterating through the list and appending each node to the appropriate list. To make list construction easier, we use dummy head nodes for both the odd and even lists. After the traversal, we link the tail of the odd list to the head of the even list.
**Time:** O(n), where n is the number of nodes in the linked list. We iterate through the list once. · **Space:** O(1) extra space. We only use a constant number of extra pointers (`oddHead`, `evenHead`, `oddTail`, `evenTail`, `curr`) regardless of the input list's size.
**Pros:** Conceptually simple and easy to understand.; Clearly separates the logic for handling odd and even nodes.
**Cons:** Uses dummy nodes, which adds a small amount of memory and code overhead.; The logic involves more pointer variables compared to a more optimized in-place solution.
### Explanation
We start by creating two dummy nodes, `oddHead` and `evenHead`, which will act as sentinel nodes for our odd and even lists. We also maintain `oddTail` and `evenTail` pointers to keep track of the last node in each list, allowing for O(1) appends.

We iterate through the original list using a `curr` pointer and a boolean flag `isOdd` to determine where to place the current node. If `isOdd` is true, we append the node to the odd list; otherwise, we append it to the even list. We then advance `curr` and toggle the flag.

After processing all nodes, the original list structure is effectively partitioned into two chains of nodes. We must terminate the even list by setting `evenTail.next` to `null`. Then, we connect the two lists by setting `oddTail.next` to the first node of the even list, which is `evenHead.next`.

The head of the reordered list is `oddHead.next`.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode oddHead = new ListNode(0);
        ListNode evenHead = new ListNode(0);
        ListNode oddTail = oddHead;
        ListNode evenTail = evenHead;
        
        ListNode curr = head;
        boolean isOdd = true;
        
        while (curr != null) {
            if (isOdd) {
                oddTail.next = curr;
                oddTail = oddTail.next;
            } else {
                evenTail.next = curr;
                evenTail = evenTail.next;
            }
            curr = curr.next;
            isOdd = !isOdd;
        }
        
        // Connect the odd list with the even list
        oddTail.next = evenHead.next;
        // Terminate the combined list
        evenTail.next = null;
        
        return oddHead.next;
    }
}
```
### Algorithm
- Handle the edge case: If `head` is null, return `null`.
- Create two dummy nodes, `oddHead` and `evenHead`, to serve as heads for the odd and even lists.
- Create tail pointers, `oddTail` and `evenTail`, initialized to the dummy heads.
- Use a boolean flag `isOdd`, initialized to `true`, to track whether the current node belongs to the odd or even group.
- Iterate through the original list with a `curr` pointer starting from `head`.
- Inside the loop:
    - If `isOdd` is true, append `curr` to the odd list and advance `oddTail`.
    - Otherwise, append `curr` to the even list and advance `evenTail`.
    - Move `curr` to the next node and flip the `isOdd` flag.
- After the loop, connect the tail of the odd list to the head of the even list (`oddTail.next = evenHead.next`).
- Crucially, terminate the now-combined list by setting the tail of the even part to null (`evenTail.next = null`).
- Return the head of the modified list, which is `oddHead.next`.

## In-place Pointer Manipulation
This is the most efficient approach, which modifies the linked list in-place without using any dummy nodes. The idea is to maintain two pointers, one for the last node of the odd-indexed group (`odd`) and one for the last node of the even-indexed group (`even`). We iterate through the list, weaving the odd and even nodes into their respective groups by rearranging the `next` pointers.
**Time:** O(n), where n is the number of nodes. We traverse the list once, and each node is visited a constant number of times. · **Space:** O(1) extra space. We only use a few extra pointers (`odd`, `even`, `evenHead`). This is a true in-place algorithm.
**Pros:** Highly efficient in both time and space, meeting the problem constraints perfectly.; Modifies the list in-place without needing extra data structures like dummy nodes.; The code is concise and elegant.
**Cons:** The pointer manipulation can be slightly harder to visualize and reason about compared to the separate lists approach.
### Explanation
First, we handle the edge cases where the list is empty or has fewer than three nodes, as no reordering is needed. We initialize an `odd` pointer to `head` (the first odd node) and an `even` pointer to `head.next` (the first even node). We also save a reference to the head of the even list, `evenHead = head.next`, because we'll need to connect the end of the odd list to it later.

We then enter a loop that continues as long as there are nodes to process, which is checked by `even != null && even.next != null`. This condition ensures we always have a pair of nodes (an even one followed by an odd one) to rearrange.

Inside the loop:
1. We link the current `odd` node to the next odd node, which is `even.next`. So, `odd.next = even.next;`.
2. We advance the `odd` pointer to this new node: `odd = odd.next;`.
3. We link the current `even` node to the next even node, which is now `odd.next`. So, `even.next = odd.next;`.
4. We advance the `even` pointer to this new node: `even = even.next;`.

After the loop terminates, the `odd` pointer will be at the tail of the odd-node sublist. We connect it to the head of the even-node sublist: `odd.next = evenHead;`. Finally, we return the original `head`.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return null;
        }
        
        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenHead = even; // Save the head of the even list
        
        // Loop while there's a pair of nodes (even and its successor) to process
        while (even != null && even.next != null) {
            // Link the next odd node
            odd.next = even.next;
            odd = odd.next;
            
            // Link the next even node
            even.next = odd.next;
            even = even.next;
        }
        
        // Connect the end of the odd list to the head of the even list
        odd.next = evenHead;
        
        return head;
    }
}
```
### Algorithm
- If `head` is null, return `null`.
- Initialize `odd` pointer to `head`.
- Initialize `even` pointer to `head.next`.
- Save the head of the even list: `evenHead = even`.
- Loop as long as `even` and `even.next` are not null.
    - Set `odd.next` to `even.next` to link the next odd node.
    - Move `odd` to `odd.next`.
    - Set `even.next` to `odd.next` to link the next even node.
    - Move `even` to `even.next`.
- After the loop, link the tail of the odd list to the head of the even list: `odd.next = evenHead`.
- Return the original `head`.

# Solutions
### Java

```java
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode oddEvenList ( ListNode head ) { if ( head == null ) { return null ; } ListNode a = head ; ListNode b = head . next , c = b ; while ( b != null && b . next != null ) { a . next = b . next ; a = a . next ; b . next = a . next ; b = b . next ; } a . next = c ; return head ; } }
```

### CPP

```cpp
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode * oddEvenList ( ListNode * head ) { if ( ! head ) { return nullptr ; } ListNode * a = head ; ListNode * b = head -> next , * c = b ; while ( b && b -> next ) { a -> next = b -> next ; a = a -> next ; b -> next = a -> next ; b = b -> next ; } a -> next = c ; return head ; } };
```

### Python

```python
# 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 ]: if head is None : return None a = head b = c = head . next while b and b . next : a . next = b . next a = a . next b . next = a . next b = b . next a . next = c return head
```