AlgoDaily - Reverse a Linked List - Complexity Of Final Solution

And we return 4 - which is pointing to 8. And we can simply extrapolate that to longer linked lists! Note that the recursive approach requires more space because we need to maintain our call stack.

Complexity of Final Solution

Let n be the number of nodes in the linked list. We traverse through all n nodes for O(n) linear time complexity. We reuse the old linked list nodes, so our space complexity is a constant O(1) as we do not allocate any extra space.

xxxxxxxxxx
    'PASSED: Reversing linked list `3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10` should return `10 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3`'
 
var assert = require('assert');
​
function reverseList(head) {
  // Fill in this method
  return head;
}
​
function Node(val) {
  this.val = val;
  this.next = null;
}
​
function LinkedListNode(val) {
  this.val = val;
  this.next = null;
}
​
var list1 = new LinkedListNode(3);
var nodes1 = [4, 5, 6, 7, 8, 9, 10];
createNodes(list1, nodes1);
​
var list2 = new LinkedListNode(1);
var nodes2 = [2, 3, 4, 5, 6, 7, 8];
createNodes(list2, nodes2);
​
function createNodes(head, nodes) {
  for (let i = 0; i < nodes.length; i++) {

OUTPUT

Results will appear here.