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!