Odd Before Even

Moderate
0/80
Average time to solve is 25m
11 upvotes
Asked in company
HSBC

Problem statement

You are given two sorted linked lists of length ‘N1’ and ‘N2’ respectively. Your task is to create a linked list with common elements such that all common odd elements are before common even elements.

Note: The relative order inside both the even and odd groups should remain as it was in the input.

You just need to return the head of the new linked list formed, don't print the elements.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’, denoting the number of test cases. Then each test case follows.

The first line of each test case contains the elements of the first singly linked list separated by a single space.

The second line of each test case contains the elements of thesecond singly linked list separated by a single space.
Output Format: 
For each test case, print a single line containing a linked list with common elements such that all common odd elements are before common even elements.

Output of each test case will be printed on a separate line.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 5
0 <= N <= 5 * 10 ^ 6
1 <= nodeVal[i] <= 10 ^ 9

Time Limit: 1 sec.
Sample Input 1:
2
1 2 3 4 5 7 8 -1
2 4 4 7 8 10 -1
1 2 7 10 20 23 -1
2 7 23 -1
Sample Output 1:
7 2 4 8
7 23 2
Explanation of Sample Input 1:
In the first test case, the common elements are {2, 4, 7, 8 }. So the elements of the new linked list is 7 -> 2 -> 4 -> 8 -> NULL as odd will come before even maintaining the relative order.

In the second test case, the common elements are {2, 7, 23 }. So the elements of the new linked list is 7 -> 23 -> 2 -> NULL as odd will come before even maintaining the relative order..
Sample Input 2:
2
10 11 12 -1
1 2 8 9 10 12 12 -1
1 2 3 3 4 -1
1 2 3 4 -1
Sample Output 2:
10 12
1 3 2  4
Hint

Since the linked list is sorted. Compare the elements using two pointers.

Approaches (1)
Two Pointer

The idea is to traverse the list until one of them becomes NULL, and maintain two lists one for ‘even’ and one for ‘odd’. Append the even list after odd list.

 

Algorithm :

 

Let ‘commonOddEven(head1, head2)’ be the function that returns the head of the common list.

The steps are as follows:

  • If head1 is NULL or head2 is NULL.
    • Return NULL
  • Take pointers 'oddHead', 'oddTail' initialize it to NULL.
  • Take pointers 'evenHead', 'evenTail' and initialize it to NULL.
  • Run a loop while 'head1' and 'head2' are not NULL:
    • If the element of 'head1' is smaller than the element of 'head2'
      • Then move 'head1' to the next node.
    • If element of 'head2' is smaller than element of 'head1':
      • Then move 'head2' to the next node.
    • Else both are equal
      • If Element is even:
        • If this element is the first node of even:
          • Initialize 'evenHead' with a new node with value 'head1 -> data'.
          • Initialize evenTail equal to 'evenHead'.
        • Else
          • Initialize 'evenTail -> next' with a new node with value 'head1 -> data'.
          • Move 'evenTail' to the next node.
      • Else
        • If this element is the first node of odd:
          • Initialize 'oddHead' with a new node with value 'head1 -> data'.
          • Make 'oddTail' equal to 'oddHead'.
        • Else
          • Initialize 'oddTail' with a new node with value 'head1 -> data'.
          • Move 'oddTail' to the next node.
        • Move 'head1' and 'head2' to the next node.
  • If there is no odd element i.e oddHead is equal to NULL:
    • Return even head ‘evenHead’.
  • Else put 'evenHead' in next of 'oddTail'.
  • Return 'oddHead'.
Time Complexity

O(min(N1, N2)),  where ‘N1’ and ‘N2’  are  the number of nodes in the given linked lists.

 

Since we are traversing the linked lists until one of them becomes null. Hence the time complexity is O(min(N1, N2)).

Space Complexity

O(min(N1, N2)), where ‘N1’ and ‘N2’  are  the number of nodes in the given linked lists.

 

In the worst case, all elements of a linked list  are common, so we need to make another linked list of space O(min(N1, N2)). So space complexity O(min(N1, N2)).

Code Solution
(100% EXP penalty)
Odd Before Even
Full screen
Console