Reverse Linked List

  • Code
  • Linked List
  • LeetCode

I'm back with another LeetCode Linked List problem, this time it's Reverse Linked List. You may recall that I wrote the .reverse() method as part of my Singly Linked List implementation a few weeks ago in my Singly Linked List blog post. The solution here is very similar to that method, with just a few adjustments to account for how LeetCode does their Linked Lists. Since this is also a classic coding interview question, I felt that it deserved its own dedicated blog post.

As an aside, I think this will be my last LeetCode solution post for a little while. I think they're great exercises (especially today's problem), but I have a lot of other things I want to learn and write about in this space. I hope you've enjoyed these solutions and found the explanations useful. I've definitely had some fun writing them. Let's get into today's problem, Reverse Linked List.

Prompt

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: []

Stating the Problem in My Own Words

I'll be writing a function that reverses a Singly Linked List in place (i.e., not creating and returning a new Linked List).

Approach: Three Variable Leap Frog

Like I mentioned earlier, I previously wrote a .reverse() method when I created my own Linked List on the Singly Linked List blog post. I've said many times at this point that LeetCode does their Linked Lists a little differently than what I've implemented (they don't track the tail or the length of the list, where my implementation does), but accounting for those differences only means minor adjustments to my code. The underlying logic is the same.

  1. Create three variables:
    1. node - assign this to equal the head
    2. prev - assign this to equal null
    3. next - don't assign anything to this variable (we'll immediately assign it in the while loop)
  2. Loop through the list
    • I previously used a for Loop that checked against the list's length property, but a while Loop that reassigns node to be the next item in the list, until node is null (at which point we've reached the end of the list) will work here.
  3. Within the loop:
    1. Assign next to be node.next
    2. Set node.next to point to prev
    3. Set prev to equal node
    4. Set node to equal next
    • These four steps create a kind of three variable leap frog as we move through the list. The current next value gets assigned to a temporary variable, the pointer gets assigned to point to the previous item, then the previous item moves up, then the current node also moves up.
  4. After the loop finishes running, return the list.
    • When we finish, prev will be the new head of the list, so we can just return prev.

Step By Step Example of Linked List Reversal

Let's say that this is our Linked List:

[1, 2, 3, 4, 5]

Or, illustrated with pointers:

1 -> 2 -> 3 -> 4 -> 5

Our solution here starts with creating the three variables, node (equal to head), prev (equal to null), and next (initially not assigned a value).

function reverseList(head) {  let node = head;  let prev = null;  let next;}

So here is where we are before we create our loop:

1 -> 2 -> 3 -> 4 -> 5- node: 1- prev: null- next: (undefined)

Now let's write our while Loop. We're going to iterate through the list starting at the head, reassigning node each time, until we reach the end of the list. We can do this by checking whether node equals null. If so, we've reached the end of the list.

Now we start looping. We immediately assign next to be node.next, storing the second item in the list into this temporary next variable. We reassign node.next to point to prev, so 1's next points to null.

null <- 1      2 -> 3 -> 4 -> 5prev    node   next

So now all we have to do is move prev up to equal node, and move node up to equal next (this step is why we created the temporary next variable), which leaves us with the following:

null <- 1      2 -> 3 -> 4 -> 5        prev   next               node- node: 2- prev: 1- next: 2

That's it for our first iteration, and we move onto the second iteration. We once again assign next to be node.next, storing the third item in the list into the temporary variable. We reassign node.next to point to prev, so 2's next points to 1.

null <- 1  <-  2      3 -> 4 -> 5        prev   node   next

Now we simply move prev up by setting it equal to node, and then move node up by setting it equal to next. This leaves us with the following:

null <- 1 <- 2      3 -> 4 -> 5             prev   next                    node- node: 3- prev: 2- next: 3

Now onto our third iteration. We reassign next to equal node.next, storing 4 into the temporary variable. We then reassign node.next to point to prev, so 3's next points to 2.

null <- 1 <- 2  <-  3      4 -> 5             prev   node   next

With next reassigned, it's time to move up prev and node by setting prev equal to node and node equal to next. This leaves us with the following:

null <- 1 <- 2 <- 3      4 -> 5                  prev   next                         node- node: 4- prev: 3- next: 4

Hopefully the pattern is becoming clear now as we move onto the fourth iteration. We reassign next to equal node.next, storing 5 into the temporary variable. We then reassign node.next to point to prev, so 4's next points to 3.

null <- 1 <- 2 <- 3  <-  4      5                  prev   node   next

Then we move prev and node up in the same manner as before.

null <- 1 <- 2 <- 3 <- 4      5                       prev   next                              node- node: 5- prev: 4- next: 5

Now it's time for our last iteration!! Move next. Remember that 5's next was previously null. Then set node.next to equal prev, making 5's next point to 4.

null <- 1 <- 2 <- 3 <- 4  <-  5      (null)                       prev   node   next

Finally we move up prev and node one more time.

null <- 1 <- 2 <- 3 <- 4 <- 5      (null)                            prev   next                                   node- node: null- prev: 5- next: null

Now that node is equal to null, our while Loop stops running. prev is at our new head, 5, and 5's next points to 4. 4's next points to 3. 3's next points to 2. 2's next points to 1. 1's next points to null, making 1 the new tail. All we have to do is return prev for LeetCode to receive this fully reversed Linked List.

return prev;

That was a lot. Let's just put our solution together.

Solution

function reverseList(head) {  let node = head;  let prev = null;  let next;
  while (node !== null) {    next = node.next;    node.next = prev;    prev = node;    node = next;  }
  return prev;}

Big O of this Solution

This solution goes through the entire Linked List once, reversing each element's pointer in place, so the runtime complexity is O(n). The reversal is done in place, without any new lists or arrays being made. There are a constant number (3) of additional variables, so it has a space complexity of O(1).