Reverse Alternate Nodes of a Singly Linked List

Moderate
0/80
profile
Contributed by
14 upvotes
Asked in companies
RupeekFlipkart limited

Problem statement

For a given Singly Linked List of integers, you are required to reverse alternate nodes and append them to the end of the list.

For Example:

The given linked list is 1->2->3->4 then after reversing the alternate nodes we will have 1->3->4->2. 

Assuming 0 based indexing, odd indexed nodes are the alternate nodes that is, in the given linked list the node with value 2 and the node with value 4 are the alternate nodes. 

List without alternate nodes:  1->3 
List with alternate nodes:  2->4 
Reversing the list with alternate nodes: 4->2

After appending the reversed alternate nodes at the end, the updated list will be 1->3->4->2.
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first and the only line of input contains the elements of the singly linked list separated by a single space and terminated by -1 and hence -1 would never be a list element.
Output format : 
For each test case, print a single line containing space-separated integers denoting the elements of the resultant linked list and ending with -1 denoting the end of the linked list.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints : 
0 <= N <= 10 ^ 6
-10 ^ 9 <= DATA <= 10 ^ 9 and DATA != -1

Where 'N' is the number of nodes in the linked list.

Time Limit: 1 sec.
Sample Input 1 :
2 4 6 8 10 -1
Sample Output 1 :
2 6 10 8 4 -1
Explanation to Sample Input 1 :
The given linked list is 2->4->6->8->10 then after reversing the alternate nodes we will have 2->6->10->8->4.


Assuming 0 based indexing, odd indexed nodes are the alternate nodes that is, in the given linked list the node with value 4 and the node with value 8 are the alternate nodes. 

List without alternate nodes:  2->6->10 
List with alternate nodes:  4->8 
Reversing the list with alternate nodes: 8->4

After appending the reversed alternate nodes at the end, the updated list will be 2->6->10->8->4.
Sample Input 2 :
-10 20 -1
Sample Output 2 :
 -10 20 -1
Hint

Try to separate the nodes which we need to reverse.

Approaches (1)
Optimal Approach
  • The idea is to segregate the nodes which we need to reverse. So let’s say the first node is at index 0, the second node is at index 1 and so on.
  • Let’s say we have two lists, the first one is called ‘even list’ which will have all the nodes which are present at the even indices in the original list and another one is called ‘odd list’ which will have all the nodes which are present at the odd indices in the original list.
  • We need to take care of the edge cases i.e it has less than three nodes in which we do not need to do anything and we can simply return the head.
  • Initialize the even list with the first node and odd list with the second node of the original list. We will be adding new alternate nodes at the front of the odd list so that it builds in the reverse order. Initially, the odd list will have only one node which will be the last node of the modified list and therefore its next node will be NULL.
  • Now traverse the original list from the second index considering two nodes per iteration. This means we will take nodes at indices 2 and 3 during the first iteration, nodes at indices 4 and 5 during the second iteration and so on till there are nodes left in the original linked list.
  • Attach the node at the even index at the end of the even list and attach the node at the odd index at the front of the odd list. At last, attach the odd list at the end of the even list. Finally, return the head node of the even list.
Time Complexity

O(N), where ‘N’ is the number of nodes in the linked list.

 

As we are traversing the linked list only once.

Space Complexity

O(1).

 

As we are using constant extra space.

Code Solution
(100% EXP penalty)
Reverse Alternate Nodes of a Singly Linked List
Full screen
Console