328. Odd Even Linked List

Odd Even the Linked List

Problem Description

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

Approach) Brute Force 

var oddEvenList = function(head) {
    if (!head) return head;
    
    var odd = head,
        even = head.next;
    // console.log({head, odd, even})
    while (odd && odd.next) {
        
        // tmp equal to memory address of even (head.next), 
       // so even will move too. 
       // Can't use even straightly because in the end we will use it.
        var tmp = odd.next;
        // console.log('begin: ', {head, even})
        
        // handle the odd to remove value of even order
        odd.next = odd.next.next;  
        // console.log('middle: ', {head, even})
        
        if ( odd.next !== null ) {
            // move odd forward to next
            odd = odd.next;
            
            // handle the even to remove value of odd order 
            tmp.next = odd.next;  
        }
        // console.log('end: ', {head, even})
    }
    
    // point the end of odd to the begin of the even
    odd.next = even;
    // console.log({head, odd, even})  
    
    return head;
};

Approach) Two Pointers

var oddEvenList = function(head) {
    if (!head) return null;
    let odd = head;
    let even = head.next;
    let evenHead = even;

    while (even && even.next) {
        odd.next = even.next;
        odd = odd.next;
        even.next = odd.next;
        even = even.next;
    }

    odd.next = evenHead;
    return head;
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem 328. Odd Even the Linked List

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!