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

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:

• n == number of nodes in the linked list
• 0 <= n <= 104
• -106 <= Node.val <= 106

Solution

/**
 * 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) {
    const dummyOdd = new ListNode(); // odd nodes
    const dummyEven = new ListNode(); // even nodes;

    let odd = dummyOdd;
    let even = dummyEven;
    let cur = head;
    let i = 1;
    while (cur) {
        if (i % 2) { // odd
            odd.next = cur;
            odd = odd.next;
        } else { // even
            even.next = cur;
            even = even.next;
        }
        cur = cur.next;
        i++;
    }

    // connect odd and even lists
    odd.next = dummyEven.next;
    even.next = null;

    return dummyOdd.next;
};

We create two linked lists, one for even indexed nodes and one for odd indexed nodes. Next, we just need to connect the two lists to get our desired result.