Problem of the day
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.
The given singly linked list is 6 -> 5 -> 3 -> 4 -> 7 -> 1 -> 2
The modified linked list should have all even values in starting and odd values in the end.
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.
2 1 3 5 6 4 7 -1
2 6 4 1 3 5 7
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
6 5 4 3 2 1 -1
6 4 2 5 3 1
1 <= 'N' <= 5000
0 <= node value <= 10^9
Where ‘N’ is the number of nodes in the linked list.
Time Limit: 1 sec
Try to divide the linked list into two parts.
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
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).
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).