Reverse a Linked List

You're sent a linked list of numbers, but it's been received in the opposite order to what you need. This has happened multiple times now, so you decide to write an algorithm to reverse the lists as they come in. The list you've received is as follows:

7 -> 2 -> 21 -> 6 -> 42 -> 10

Write an algorithm for a method reverseList that takes in a head node as a parameter, and reverses the linked list. It should be capable of reversing a list of any length.

You may use the example linked list for testing purposes. Your method will be called as such:

class LinkedListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

l1 = new LinkedListNode(1);
l1.next = new LinkedListNode(2);
reverseList(l1);

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

l1 = Node(1)
l1.next = Node(2)
reverse_list(l1)

Constraints

• Length of the given LinkedList <= 100000
• The nodes will always contain integer values between -1000000000 and 1000000000
• Expected time complexity : O(n)
• Expected space complexity : O(1)

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:

17 -> 2 -> 21 -> 6 -> 42 -> 10

becoming

17 <- 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.

There are many ways to do the actual reversal, and we'll cover both an iterative and recursive approach, but the general methodology is as follows:

1. Begin by creating 3 pointers: newHead, head and nextNode.
   1. newHead and nextNode are initialized to null.
   2. head starts off pointing to the head of the linked list.
2. Iterate (or recursively do) through the following process until head is null. This means that the end of the list has been reached:

```js
class LinkedListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

l1 = new LinkedListNode(1);
l2 = new LinkedListNode(2);
l1.next = l2;

// we start at head
let head = l1;
let newHead = null;
while (head != null) {
  // store the node to the right to reuse later
  let nextNode = head.next;
  // set the current node's next to point backwards 
  head.next = newHead;
  // store the current node, to be used as the new next later
  newHead = head;
  // the previously right-side node is now processed
  head = nextNode;
}

console.log(l2);
```
```py
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

l1 = Node(1)
l1.next = Node(2)

def reverse_list(head):
    prev = None
    nextNode = None
    # we start at head
    current = head

    if not head:
        return

    while current is not None:
        # store the node to the right to reuse later
        nextNode = current.next
        # set the current node's next to point backwards 
        current.next = prev
        # store the current node, to be used as the new next later
        prev = current
        # the previously right-side node is now processed
        current = nextNode

    return prev

def list_to_str(head):
    new_arr = []
    while head:
        new_arr.append(str(head.val))
        head = head.next
    return " -> ".join(new_arr)

print(list_to_str(reverse_list(l1)))
```

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!

It'll be especially difficult while balancing your nerves and talking to the interviewer. Take advantage of the whiteboard not just to record things, but also to think through potential steps.

Let's walk through it step by step and then look at working code. Let's reverse an extremely basic list, like 8 -> 4. The first line is let nextNode = head.next;, which will store the node to the right.

```js
nextNode = 4
// 8 -> 4
```

Then we'll do head.next = newHead;, which will set the current node's next to point backwards.

```js
nextNode = 4
// <- 8, 4
```

Now newHead = head; will store the current node, to be used as the new next later.

```js
newHead = 8
nextNode = 4
// <- 8, 4
```

Finally, the previously right-side node is now processed:

```js
newHead = 8
nextNode = 4
// <- 8, 4
         ^
   current node
```

Now we process the next one with the same steps. nextNode = head.next; will store the node to the right.

```js
newHead = 8
nextNode = null
// <- 8, 4
         ^
   current node
```

Again, set the current node's next to point backwards with head.next = newHead;. Recall that newHead is 8! This is where we make the switch:

```js
newHead = 8
nextNode = null
// <- 8 <- 4
           ^
     current node
```

Now let's see this all put together in code, with lots of comments for edification!

```js
class LinkedListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

l1 = new LinkedListNode(8);
l2 = new LinkedListNode(4);
l1.next = l2;

// start at head, 8
let head = l1;
// example: 8 -> 4
let newHead = null;
while (head) {
  /* FIRST PASS */
  // store the node to the right
  let nextNode = head.next;
  // nextNode = 4, still 8 -> 4
  // set the current node's next to point backwards
  head.next = newHead;
  // 8 -> null
  // store the current node, to be used as the new next later
  newHead = head;
  // newHead = 8
  // the previously right-side node is now processed
  head = nextNode;
  // head = 4

  /* SECOND PASS */
  // store the node to the right
  nextNode = head.next;
  // nextNode = null
  // set the current node's next to point backwards
  head.next = newHead;
  // 4 -> 8
  // store the current node as the previous one
  newHead = head;
  // the previously right-side node is now processed
  head = nextNode;
}

console.log(l2);
```
```py
class Node:
  def __init__(self, val, next = None):
    self.val = val
    self.next = next


l1 = Node(8)
l2 = Node(4)
l1.next = l2

# start at head, 8
head = l1
# example: 8 -> 4
newHead = None
while head:
  # FIRST PASS
  # store the node to the right
  nextNode = head.next
  # nextNode = 4, still 8 -> 4
  # set the current node's next to point backwards
  head.next = newHead
  # 8 -> null
  # store the current node, to be used as the new next later
  newHead = head
  # newHead = 8
  # the previously right-side node is now processed
  head = nextNode
  # head = 4

  # SECOND PASS
  # store the node to the right
  nextNode = head.next
  # nextNode = null
  # set the current node's next to point backwards
  head.next = newHead
  # 4 -> 8
  # store the current node as the previous one
  newHead = head
  # the previously right-side node is now processed
  head = nextNode
  
def list_to_str(head):
    new_arr = []
    while head:
        new_arr.append(str(head.val))
        head = head.next
    return " -> ".join(new_arr)

print(list_to_str(l2))
```

Does that all make sense? Be sure to go through the iterative approach a few times.

Here's the recursive way to do it. This can also be tricky, especially on first glance, but realize most of the magic happens when it gets to the end.

```js
class LinkedListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

l1 = new LinkedListNode(8);
l2 = new LinkedListNode(4);
l1.next = l2;

function reverseList(head) {
  if (!head || !head.next) {
    return head;
  }

  let rest = reverseList(head.next);

  head.next.next = head;
  delete head.next;
  return rest;
}

console.log(reverseList(l1));
```
```py
class Node:
  def __init__(self, val, next = None):
    self.val = val
    self.next = next

l1 = Node(8)
l2 = Node(4)
l1.next = l2

def list_to_str(head):
    new_arr = []
    while head:
        new_arr.append(str(head.val))
        head = head.next
    return " -> ".join(new_arr)

def reverseList(head):
  if (not head) or (not head.next):
    return head

  rest = reverseList(head.next)

  head.next.next = head
  head.next = None
  return rest

print(list_to_str(l1))
```

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:

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

if not head or not head.next:
  return head

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

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

# remember, head is 8 - it is being processed
# head.next is 4
head.next.next = head
# head.next.next was null since 4 wasn't pointing to anything
# but now head.next (4) points to 8

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.

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.