Odd Even Linked List
1. You are given a partially written LinkedList class.Input Format
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 is managed for youOutput Format
Output is managed for youQuestion Video
1. Time complexity > O(n)Sample Input
2. Space complexity > constant
7Sample Output
2 8 9 1 5 4 3
10
100
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 nonempty. 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(){ LinkedList odd = new LinkedList(); LinkedList even = new LinkedList(); while(this.size > 0){ int val = this.getFirst(); this.removeFirst(); if(val % 2 == 0){ even.addLast(val); } else { odd.addLast(val); } } if(odd.size > 0 && even.size > 0){ odd.tail.next = even.head; this.head = odd.head; this.tail = even.tail; this.size = odd.size + even.size; } else if(odd.size > 0){ this.head = odd.head; this.tail = odd.tail; this.size = odd.size; } else if(even.size > 0){ this.head = even.head; 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.

Asked in Companies

Related Topics