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
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






Video Solution

Code Solution

Run
 
Run
Id Name