Odd Even Linked List

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

7
2 8 9 1 5 4 3
10
100

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(){
                                      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