LL 10 - Segrregate odd and even nodes

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. (link)

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

Solution

Brute force Approach

All the odd nodes will be at the front, followed by even nodes. Note that the indexing of the linked list mentioned here is not 0-based; the index of the linked list starts with 1.

Here, we collect all the odd nodes into a list and then append all the even nodes into the same list. Now, we have the correct sequence of values: odd nodes at the front followed by even nodes in the list. We simply copy the same sequence into the linked list.

Time - O(n/2) + O(n/2) + O(n) = O(n)

Space - O(n)

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

        List<Integer> ans = new ArrayList<>();
        ListNode temp = head;

        while(temp!=null && temp.next!=null){
            ans.add(temp.val);
            temp = temp.next.next;
        }

        if(temp!=null) ans.add(temp.val);

        temp = head.next;

        while(temp!=null && temp.next!=null){
            ans.add(temp.val);
            temp = temp.next.next;
        }

        if(temp!=null) ans.add(temp.val);

        temp = head;

        for(int element: ans){
            temp.val = element;
            temp = temp.next;
        }

        return head;
    }
}

Optimal Approach

In this method, we utilize two pointers named odd and even. These pointers sequentially create odd and even number sequences, respectively, within a single iteration.

The odd sequence is formed by altering the address of the current node in the following manner:

odd.next = odd.next.next

Similarly, the even sequence is created by:

even.next = even.next.next

We perform these alterations simultaneously, directing odd to the next odd-numbered node and even to the next even-numbered node.

It's worth noting that we preserve the head of the even sequence as evenHead and connect this evenHead to the end of the odd sequence.

Time - O(n)

Space - O(1)

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

        ListNode evenHead = head.next;
        ListNode odd = head;
        ListNode even = evenHead;

        while(even!=null && even.next!=null){
            odd.next = odd.next.next;
            even.next = even.next.next;

            odd = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}