Last Updated: 3 Dec, 2020

Odd Before Even

Moderate

Asked in company

Solve now

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.

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.

Solve now

Approaches

01 Approach

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

Solve now