Segregate Even And Odd Nodes In a Linked List

Easy
0/40
Average time to solve is 15m
profile
Contributed by
89 upvotes
Asked in companies
OlaPaytm (One97 Communications Limited)Dunzo

Problem statement

You are given the head node of a singly linked list 'head'. Your task is to modify the linked list in such a way that all the even valued nodes appear before the all odd valued node and order of nodes remain the same.


Example :-
The given singly linked list is  6 -> 5 -> 3 -> 4 -> 7 -> 1 -> 2 

subsequence

The modified linked list should have all even values in starting and odd values in the end.
Detailed explanation ( Input/output format, Notes, Images )
Input Format :-
The first line contains space-separated integers denoting the values of nodes of the Linked List. The Linked List is terminated with -1. Hence, -1 is never a node value of the Linked List.
Output Format :-
Print space-separated integers denoting the elements of the modified linked list.
Note :-
You do not need to print anything; it has already been taken care of. Just implement the given function.
Sample Input 1
2 1 3 5 6 4 7 -1
Sample Output 1
2 6 4 1 3 5 7
Explanation of Sample Input 1
Given singly linked list 2 -> 1 -> 3 -> 5 -> 6 -> 4 -> 7.

Arrange all the even values in the starting and odd values at the end of the linked list.

So ‘2, 6, 4’ must appear in the starting and ‘1, 3, 5, 7’ must appear at the end of linked list 

So return 2 -> 6 -> 4 -> 1 -> 3 -> 5 -> 7
Sample Input 2
6 5 4 3 2 1 -1
Sample Output 2
6 4 2 5 3 1
Constraints :-
1 <= 'N' <= 5000
0 <= node value <= 10^9  

Where ‘N’ is the number of nodes in the linked list.

Time Limit: 1 sec
Hint

Try to divide the linked list into two parts.

Approaches (1)
Brute Force Approach

The basic idea is to divide the linked list into two parts - odd and even. The even linked list will contain only nodes whose value is even and vice - versa for the odd linked list. Finally, we will attach the odd linked list after the even linked list.

 

Algorithm

 

  • Use four pointers ‘evenStart =null’, ‘oddStart =null’, ‘evenLast =null’, ‘oddLast =null’.
  • Copy the ‘head’ of the linked list in ‘current= head’ variable.
  • Iterate the linked list while it’s not null:
    • Let our current node be ‘currVal’. Then ‘currVal= current->val’.
    • If ( currVal %2==0 ), then it is a part of the even values linked list.
      • if( evenStart==null) then it is the first node of the even values linked list.
        • We set the variables ‘evenStart= current’ and ‘evenEnd= evenStart’
      • Else, even values linked list has already some nodes so-
        • Add ‘evenEnd ->next =current’ and ‘evenEnd= evenEnd’
  • Else then it is a part of odd values linked list.
    • if( oddStart==null) then it is the first node of odd values linked list.
      • We set the variables ‘oddStart= current’ and ‘oddEnd= oddStart’
    • Else, odd linked list has already some nodes so-
      • Add ‘oddEnd ->next =current’ and ‘oddEnd= oddEnd’
  • Now we have created two even and odd separate linked list(ll),
  • if(oddStart == null or evenStart == null), it means we don't need to do anything just return the linked list ‘head’.
  • Else concatenate the both even and odd linked list with ‘head’ by-
    • evenEnd ->next = oddStart
    • oddEnd -> next = null
    • head= endStart
  • We finally return ‘head’
Time Complexity

O(N), Where ‘N’ is the size of the given singly linked list.

 

As every element of the linked list will be visited at most one the time complexity will be O(N).

Space Complexity

O(N), Where ‘N’ is the size of the given singly linked list.

 

As every element of the linked list will be copied into ‘evenStart’ or ‘oddStart’ the space complexity will be O(N).

Code Solution
(100% EXP penalty)
Segregate Even And Odd Nodes In a Linked List
Full screen
Console