One Pager Cheat Sheet

• You need to write a reverseList algorithm that takes in a head node as a parameter and reverses a linked list of any length in O(n) time with O(1) space.
• To reverse a linked list, simply flip each pointer, so that the next references the previous node.
• It takes time and effort to properly reverse a linked list, so be sure to use recursion and draw diagrams to help keep your progress on track.
• The general methodology for reversing a linked list involves a combination of iterative and recursive techniques that involve creating and manipulating 3 pointers: newHead, head and nextNode.
• Keep track of the interview flow by using online comments or, if on a whiteboard, diagrams to help visualize the sequence of events.
• Take advantage of the whiteboard to think through potential steps for reversing an technical term list, and then look at working code.
• We will change the node's next reference to point to the previous node, using head.next = newHead;.
• Storing the current node in newHead will be used as the next later.
• The right-side node is now processed and has become the previous node.
• We store the node to the right by setting nextNode = head.next; and repeat the same process with the next node.
• We make the switch by setting the current node's next to newHead, which is 8.
• We can See how all the key concepts are put together in code, with lots of explaining comments!
• The recursive approach to this can be tricky, especially on first glance, but most of the magic happens when it reaches the end.
• The reverseList function is called on 4, which reaches the termination clause due to there being no .next.
• 4 was originally not pointing to anything, but after head.next.next = head it now points back to 8.
• We have achieved O(n) linear time complexity and O(1) space complexity when traversing a linked list and reusing the old nodes.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

var assert = require('assert');

​

// iterative

function reverseList(head) {

  if (head.length < 2) {

    return;

  }

​

  let newHead = null;

  while (head != null) {

    let nextNode = head.next;

    head.next = newHead;

    newHead = head;

    head = nextNode;

  }

  return newHead;

}

​

// recursive

function reverseList(head) {

  if (!head || !head.next) {

    return head;

  }

​

  let rest = reverseList(head.next);

​

  head.next.next = head;

  delete head.next;

  return rest;

}

​

function Node(val) {

Got more time? Let's keep going.

If you had any problems with this tutorial, check out the main forum thread here.