Problem of the day
You are given a Singly Linked List of integers. You need to reverse the Linked List by changing the links between nodes.
Note :You do not need to print anything, just return the head of the reversed linked list.
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.
1 <= 'N' <= 10^4
0 <= 'data' <= 10^9
Where 'N' is the number of nodes in the linked list.
Time Limit: 1 sec
1 2 4 -1
4 2 1 -1
1->2->4 is the initial linked list. If we reverse this, we get 4->2->1.
1
1 1 1 -1
1 1 1 -1
Use recursion to reverse the linked list.
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
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).
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).