Reverse Linked List

Easy
0/40
Average time to solve is 15m
profile
Contributed by
199 upvotes
Asked in companies
IBMBig BasketSAP Labs

Problem statement

Note :
You do not need to print anything, just return the head of the reversed linked list. 
Detailed explanation ( Input/output format, Notes, Images )
Input Format :
The first line contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.
Output Format :
Print the reversed linked list. The elements of the reversed list should be single-space separated, terminated by -1.
Constraints :
1 <= 'N' <= 10^4
0 <= 'data' <= 10^9

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

Time Limit: 1 sec
Sample Input 1 :
1 2 4 -1
Sample Output 1 :
4 2 1 -1
Explanation for Sample Input 1 :
1->2->4 is the initial linked list. If we reverse this, we get 4->2->1.
Sample Input 2 :
1
1 1 1 -1
Sample Output 2 :
1 1 1 -1
Hint

Use recursion to reverse the linked list.

Approaches (2)
Recursive Approach

One way is to use recursion to reverse the list. Divide the linked list in two halves, the first node and the rest of the list. Reverse the second half using recursion and append the first half, that is the first node at the end of the reversed linked list. Return the head of the reversed linked list.

 

Algorithm

 

  • If the list contains only one node, return the head of the list.
  • Else, divide the list into two parts, first node and the rest of the linked list.
  • Call the reverse for the rest of the linked list.
  • Append the first node at the end of the reversed linked list, the linked list obtained in step 2.
  • Return the head of the reversed linked list, obtained in step 4.
Time Complexity

O(n), Where ‘n’ is the number of nodes in the linked list.

 

There can be at most ‘n’ recursive states while reversing the linked. We are traversing the list only once, thus the final time complexity is O(n).

Space Complexity

O(n), Where ‘n’ is the number of nodes in the linked list.

 

There can be at most ‘n’ recursive states which will take O(n) space. Thus, the final space complexity is O(n).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Reverse Linked List
Full screen
Console