Let's take the most basic linked list first-- one with two nodes. We need to reverse this.

Seems pretty easy, right? To reverse an entire linked list, simply reverse every pointer. If 1 is pointing at 2, flip it so 2 should point to 1.

Of course, there's complexities that lie ahead. But for now, that's the basis for:

117 -> 2 -> 21 -> 6 -> 42 -> 10

becoming

117 <- 2 <- 21 <- 6 <- 42 <- 10

The actual reversal method is actually pretty straightforward, but be aware that it takes some time to reason out. It's easy to get lost, so make sure you draw lots of diagrams.

As this is a problem (reversing an entire linked list) that can be broken up into sub-problems (reverse the pointer between just two nodes), it seems like a good opportunity to use recursion.

It's difficult to visualize this chain of events, so let's use comments to visualize it. During the interview, try not to keep it in your head.

Here's a pro-tip: many interviews are conducted online now, so you'll be able to type out things. You can use ASCII-esque linked lists like 1 -> 2 -> 3 to keep the directionality clear. If you're still on a whiteboard, diagram away!

Let's take an easy example of 8 -> 4 again. let rest = reverseList(head.next); takes 4 and calls reverseList on it.

Calling reverseList on 4 will have us reach the termination clause because there is no .next:

1if (!head || !head.next) {
2  return head;
3}

We go up the stack back to when 8 was being processed. rest now simply points to 4. Now notice what happens:

1// remember, head is 8 - it is being processed
2// head.next is 4
3head.next.next = head;
4// head.next.next was null since 4 wasn't pointing to anything
5// but now head.next (4) points to 8

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) {

  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++) {

    var newNode = new LinkedListNode(nodes[i]);

    head.next = newNode;

    head = newNode;

  }

}

​

try {

  var reversed = reverseList(list1);

  assert.deepEqual(

    listToString(reversed),

    '10 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3'

  );

​

  console.log(

    'PASSED: Reversing linked list `3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10` should return `10 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3`'

  );

} catch (err) {

  console.log(err);

}

​

function listToString(head) {

  var toPrint = [];

  var currNode = head;

  while (currNode) {

    toPrint.push(currNode.val);

    currNode = currNode.next;

  }

  return toPrint.join(' -> ');

}

Great job getting through this. Let's move on.

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