328. Odd Even Linked List

Hello, reader 👋🏽 ! Welcome to day 66 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 328. Odd Even Linked List.

🤔 Problem Statement

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.
The problem must be solved in in O(1) extra space complexity and O(n) time complexity.
E.g:
- head = [1,2,3,4,5] => [1,3,5,2,4]
- head = [1,2,3,4,5,6] => [1,3,5,2,4,6]

💬 Thought Process - Traverse List

We need to group all the even nodes together and all the odd nodes together. Then the odd nodes tail must point to the head of the even nodes.
It can be seen that the first node (the node head points to) in the original list is the odd node.
Hence, the node we shall return would be the head of the list.
The even node would be the next node after the node head points to in the list.
It could be possible that the list is itself null. hence before iterating and setting the odd and even heads, we must check this and return null if list is null.
Now, we must start iterating the list with two pointers: one with the current odd node and another with current even node.
The iteration would begin from the even pointer, i.e., is the starting node for the grouped list of nodes at even indices.
Now at every iteration, the next node of the odd pointer would be the next node of the even pointer.
- In this case, node with value 2 is the node odd pointer is currently at.
- The next node for odd pointer would be node with value 4.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1670347839321/AT7WmcSCz.png align="left")

Now that the odd pointer has been updated, we need to set the next node for the even pointer.
- We can do this by setting the next node of odd pointer. In this case, node with value 5.
- Hence, node with value 3 at index 2 will point to the node with value 5.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1670348036998/oeMtV-hb0X.png align="left")

We keep repeating this process until either the even pointer becomes null or the next node of the even pointer is null.
In case of odd number of nodes, the even pointer would eventually point to the end of the list and at this point we stop.
But in case of even number of nodes, the even pointer would eventually point to the last node and at this point we stop.
After the iteration we will update the odd pointer, which points to the tail of the odd list, to point to the head of the even nodes list.
- Below are the remaining two steps in the above example.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1670348306102/NYSyzeg6Z.png align="left")

Below is the example when the number of nodes is odd.

👩🏽‍💻 Solution - Traverse List

Below is the code for the approach using getting the length and returning length/2 element.

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

        ListNode oddPtr = head;
        ListNode evenPtr = head.next;

        ListNode evenHead = evenPtr;
        ListNode oddHead = head;

        while(evenPtr != null && evenPtr.next != null) {
            oddPtr.next = evenPtr.next;
            oddPtr = oddPtr.next;

            evenPtr.next = oddPtr.next;
            evenPtr = evenPtr.next;
        }

        oddPtr.next = evenHead;

        return head;
    }
}

Time Complexity: O(n)
  - n = number of nodes in the list
Space Complexity: O(1)

You can find the link to the GitHub repo for this question here: 328. Odd Even Linked List.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!

Bharati Subramanian