Odd Even Linked List

---

Odd Even Linked List: 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

---

Try this Problem on your own or check similar problems:

1. Split Linked List in Parts

Solution:

Java

public ListNode oddEvenList(ListNode head) {
    if(head == null || head.next == null) return head;

    ListNode dummy = new ListNode(-1, head), iter = dummy.next, headOfEven = iter.next;
    ListNode even = new ListNode(-1, head), odd = new ListNode(-1, head);
    boolean isEven = false;

    while(iter != null){
      if(isEven){
          even.next = iter;
          even = even.next;
      }
      else{
          odd.next = iter;
          odd = odd.next;
      }
      iter = iter.next;
      isEven = !isEven;
    }
    even.next = null;
    odd.next = headOfEven;

    return dummy.next;
}

JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var oddEvenList = function (head) {
  if (head === null || head.next === null) return head;

  const dummy = new ListNode(-1, head);
  let iter = dummy.next;
  let headOfEven = iter.next;
  let even = new ListNode(-1, head);
  let odd = new ListNode(-1, head);
  let isEven = false;

  while (iter !== null) {
    if (isEven) {
      even.next = iter;
      even = even.next;
    } else {
      odd.next = iter;
      odd = odd.next;
    }
    iter = iter.next;
    isEven = !isEven;
  }
  even.next = null;
  odd.next = headOfEven;

  return dummy.next;
};

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 or head.next is None:
            return head

        dummy = ListNode(-1, head)
        iter = dummy.next
        headOfEven = iter.next
        even = ListNode(-1, head)
        odd = ListNode(-1, head)
        isEven = False

        while iter is not None:
            if isEven:
                even.next = iter
                even = even.next
            else:
                odd.next = iter
                odd = odd.next
            iter = iter.next
            isEven = not isEven

        even.next = None
        odd.next = headOfEven

        return dummy.next

C++

/**
 * 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 == nullptr || head->next == nullptr)
            return head;

        ListNode* dummy = new ListNode(-1, head);
        ListNode* iter = dummy->next;
        ListNode* headOfEven = iter->next;
        ListNode* even = new ListNode(-1, head);
        ListNode* odd = new ListNode(-1, head);
        bool isEven = false;

        while (iter != nullptr) {
            if (isEven) {
                even->next = iter;
                even = even->next;
            } else {
                odd->next = iter;
                odd = odd->next;
            }
            iter = iter->next;
            isEven = !isEven;
        }

        even->next = nullptr;
        odd->next = headOfEven;

        return dummy->next;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

---

Explanation:

We create two new nodes even and odd, both pointing to the head. As always, we have the dummy pointer pointing to the head of the list along with iter which we will use to iterate over the linked list. We have a helper variable isEven which we use to decide to which list (odd or even) we add the current iter node. We must not forget to break the connection between the last even node and last odd node even.next = null, if we don't do this we will have cycle in the linked list, also we have to connect the last odd node with the first even (we use headOfEven for that). You can think of the algorithm as having an iter going to end of the linked list each time reconnecting (changing the next relation) to either odd or even node. We return dummy.next since it points to the head of the modified list. Since we traverse the whole original list we have linear time complexity, with constant space complexity since we don't create any additional data structures.