Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Example 2:
Input: head = [1,2]
Output: [2,1]
Example 3:
Input: head = []
Output: []
Pseudocode
initial intuition is to replace node.val but without an array it's not possible to retrieve the first node val when recursing the last value
instead, just extend the last node, node.next to previous e.g.
1 -> 2 -> 3 -> 4 -> 5
5 -> 4 -> 3 -> 2 -> 1
new reverse node is returned at the end of each recursion, adding the prev value to node.next. remember that objects are passed by reference
Solution
var reverseList = function (head) {
return walk(head, null);
};
function walk(node, prev) {
if (!node) {
return prev;
}
const extend = walk(node.next, node);
node.next = prev;
return extend;
}
Time and Space Complexity
Time
Linked list has to be traversed to the end and reassigned next to previous - O(N)
