Odd Even Linked List

Odd-Even Linked List

Difficulty: Medium

Understanding The Problem

Problem Description

Given a singly linked list, write a program to group all odd nodes together followed by the even nodes.

Problem Note

Please note here we are talking about the node number and not the value in the nodes.
You should try to do it in place.
The program should run in O(n) time complexity.
The relative order inside both the even and odd groups should remain as it was in the input.
The first node is considered odd, the second node even, and so on.

Example 1

Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL
Explanation: The first group is of elements at odd position (1,3,5) in the linked list and then the ones at the even position(2,4)

Example 2

Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL
Explanation: The first group is of elements at odd position (2,3,6,7) in the linked list and then the ones at the even position(1,5,4)

You should have a clear understanding of a linked list to solve the problem.

You may try to solve this problem here .

Solution

The problem could have various possible solutions in which you can use an auxiliary space to store the numbers in order and recreate a linked list but the question explicitly demands the time complexity to be O(n) and to be solved in-place.

So the basic idea is that we can put all the odd positioned nodes in a linked list and all the even positioned nodes in another linked list, and we can simply join them end to end.

In short, we will have two pointers. The first will point to the head and the second will point to the next of the head. Now in each iteration, each of the pointers will skip one element add the even positioned and odd positioned nodes respectively. This will allow us to use the same linked list and save us from using auxiliary space.

Look at the following diagram of example 1 to get a clear picture of how the linked list is being manipulated.

Solution Steps

Take two pointers oddPointer and evenPointer
and maintain head pointers too.
Now, Do below process until evenPointer becomes null

Delete one node in the odd list and move two steps forward.
Delete one node in even list and move two steps forward.

3. Now, merge odd and even lists.

This can be done by oddPointer.next = even_head
oddPointer points to the last node in the odd list
We need to add the even list at the end of the odd list.

4. Return the resultant list.

Pseudo Code

ListNode oddEvenList(ListNode head) {
    if(head == nullptr or head->next == nullptr) 
        return head
    ListNode oddPointer = head
    ListNode evenPointer = head.next
    ListNode even = head.next
    while(evenPointer != null and evenPointer.next != null){
        oddPointer.next = oddPointer.next.next
        oddPointer = oddPointer.next
        evenPointer.next = evenPointer.next.next
        evenPointer = evenPointer.next
    }
    oddPointer.next = even
    return head
}

Complexity Analysis

Time Complexity: O(n) (How?)

Space Complexity: O(1)

Critical Ideas To Think

What do oddPointer and evenPointer represent?
Why did we initialize evenPointer with head.next ?
We created an even variable to store the head of evenPointer. How does this help to solve the problem?
The even list has n/2 nodes. Why does the solution have O(1) space complexity? Answer: Since we are not creating any new nodes here, space complexity is O(1). we are just creating three new pointers overall irrespective of the input. So the space remains constant.
Can we conclude that we are just adding the even nodes at the end of the linked list every time until the original list is over?