Reverse Linked List

Reverse Linked List - LeetCodeLeetCode

Problem

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)

• Total - O(N)

Space

• A reverse linked list was returned - O(N)

• Total - O(N)