# Odd Even Linked List #### Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

`1. You are given a partially written LinkedList class.2. You are required to complete the body of oddEven function. The function is expected to tweak the list such that all odd values are followed by all even values. The relative order of elements should not change. Also, take care of the cases when there are no odd or no even elements. Make sure to properly set head, tail and size as the function will be tested by calling addFirst and addLast.3. Input and Output is managed for you.`
Input Format
`Input is managed for you`
Output Format
`Output is managed for you`
Question Video
Constraints
`1. Time complexity -> O(n)2. Space complexity -> constant`
Sample Input
`72 8 9 1 5 4 310100`
Sample Output
`2 8 9 1 5 4 3 9 1 5 3 2 8 4 10 9 1 5 3 2 8 4 100 `

• Editorial

The problem deals with modifying the input list such that all odd values follow all even values. For example the list is 1 -> 2 -> 3 -> 4 -> 5 -> 7 -> 6 -> 9 -> 8 so our output should be 1 -> 3 -> 5 -> 7 -> 9 -> 2 -> 4 -> 6 -> 8.

To achieve this we will be taking two lists, one for storing odd values and the other for storing even values. Now we iterate over the input list and segregate every element by checking whether it is an odd or even element. Later on, we combine both the list by adding an even list at the tail of the odd list and then update the linked list data member by this resultant list.

After segregation, we have taken three cases:

1. odd.size() > 0 and even.size() > 0

This is the general case when both lists are non-empty. Here we first add the even list at the end of the odd list, later on, we update the linked list data member with the resultant combined list.

2. odd.size() > 0 and even.size() == 0

This is the case when our even list is empty, in this case, the odd list is our result, so we just need to update the data member list with an odd list.

3. odd.size() == 0 and even.size() > 0

This is the case when our odd list is empty, in this case, the even list is our result, so we just update the data member list with an even list.

Below is the implementation in Java:

```public void oddEven(){

while(this.size > 0){
int val = this.getFirst();
this.removeFirst();

if(val % 2 == 0){
} else {
}
}

if(odd.size > 0 && even.size > 0){

this.tail = even.tail;
this.size = odd.size + even.size;
} else if(odd.size > 0){
this.tail = odd.tail;
this.size = odd.size;
} else if(even.size > 0){
this.tail = even.tail;
this.size = even.size;
}
}```

java false

Dry Run

Input List: 1 -> 2 -> 3 -> 4 -> 5 -> 7 -> 6 -> 9 -> 8

Output List: 1 -> 3 -> 5 -> 7 -> 9 -> 2 -> 4 -> 6 -> 8

Initially, even and odd both lists are empty.

First Iteration

this.size() = 9 != 0

val= 1

removeFirst()

val % 2 != 0, therefore odd.add(1)

List: 2 -> 3 -> 4 -> 5 -> 7 -> 6 -> 9 -> 8

Even:

Odd: 1

Second Iteration

this.size() = 8 != 0

val= 2

removeFirst()

val % 2 == 0, therefore even.add(2)

List: 3 -> 4 -> 5 -> 7 -> 6 -> 9 -> 8

Even: 2

Odd: 1

Third Iteration

this.size() = 7 != 0

val= 3

removeFirst()

val % 2 != 0, therefore odd.add(3)

List: 4 -> 5 -> 7 -> 6 -> 9 -> 8

Even: 2

Odd: 1 -> 3

Fourth Iteration

this.size() = 6 != 0

val= 4

removeFirst()

val % 2 == 0, therefore even.add(4)

List: 5 -> 7 -> 6 -> 9 -> 8

Even: 2 -> 4

Odd: 1 -> 3

Fifth Iteration

this.size() = 5 != 0

val= 5

removeFirst()

val % 2 != 0, therefore odd.add(5)

List: 7 -> 6 -> 9 -> 8

Even: 2 -> 4

Odd: 1 -> 3 -> 5

Sixth Iteration

this.size() = 4 != 0

val= 7

removeFirst()

val % 2 != 0, therefore odd.add(7)

List: 6 -> 9 -> 8

Even: 2 -> 4

Odd: 1 -> 3 -> 5 -> 7

Seventh Iteration

this.size() = 3 != 0

val= 6

removeFirst()

val % 2 == 0, therefore even.add(6)

List: 9 -> 8

Even: 2 -> 4 -> 6

Odd: 1 -> 3 -> 5 -> 7

Eight Iteration

this.size() = 2 != 0

val= 9

removeFirst()

val % 2 != 0, therefore odd.add(9)

List: 8

Even: 2 -> 4 -> 6

Odd: 1 -> 3 -> 5 -> 7 -> 9

Ninth Iteration

this.size() = 1 != 0

val= 8

removeFirst()

val % 2 == 0, therefore even.add(8)

List:

Even: 2 -> 4 -> 6 -> 8

Odd: 1 -> 3 -> 5 -> 7 -> 9

Tenth Iteration

this.size() == 0

Loop breaks

As odd.size()> 0 andeven.size() > 0

Output List: [odd] + [even] = 1 -> 3 -> 5 -> 7 -> 9 -> 2 -> 4 -> 6 -> 8

Hence our algorithm is verified.

Time Complexity: O(n)

The time complexity for the function is linear as we are traversing on every node and updating the odd and even lists which is dependent on the length of the linked list.

Space Complexity: O(n)

The space complexity for the function is linear as we have created two lists that combined are storing all the elements of the input list which too depends on the size of the list.

• Related Topics

Run

Run
Id Name