Today, I think I finally learned how to reverse a linked list. This isn't the only thing I did with linked lists, but it did give me the sort of giddy aha moment that begs to be shared with others. It feels like the whole exercise finally just clicked.
But instead of copying and pasting my JavaScript solution, wouldn't it be more fun to lay out my thought process to this solution? Maybe there's still some part I'm completely misunderstanding. In which I would definitely want to know.
1)
Declare 3 variables that will act as your 3 pointers: prev, current, next
- current is the node you start with (aka the head of your list)
- next is the pointer to your next node (aka the link to the node after current)
- prev is the node before current. In this case, null because there's nothing before the head node
let current = this.head
let next = current.next
let prev = null
2)
Before we get started with anything else, notice that current is at the top of your file before we swap the head and tail values.
let current = this.head
this.head = this.tail // <---
// we're swapping these two |
this.tail = this.head // <---
let next = current.next
let prev = null
- Keep in mind that following this order swaps the values but not the references to the next node. The reason we set declare
current
first is that we want to pass on the reference to our current node. - But once we do
this.head = this.tail
, our head node has its next property replaced withnull
. This is because the tail is the last node andthis.tail.next
is alwaysnull
. - Now, our head and tail nodes are just chilling out in the ether with no next references.
this.head.next
is alsonull
.
3)
Declare a counter variable to keep track of our loop
let counter = 0
4)
Next is the part I found to be the trickiest. Within a while loop, we're basically moving our pointers in such a way that the values of our nodes are being stashed and then updated
- To start, update our pointers in the following order:
- bump up next
- bump up prev
- bump up current
- Each time you loop through, this is what your pointers will look:
- next => points to D2 => points to D3...
- previous => null => D1...
- current => D1 => D2...
// bump up next node
next = current.next
// bump up previous node
current.next = prev //**
prev = current
// bump up current node
current = next
counter++
*** notice that we're also flipping where our .next is pointing
Remember that a node has 2 properties: a value and a link/pointer to the next node.
(source: freeCodeCamp)
What we're doing here is altering this link so that it points to the node before it, instead of the node after. Each time you loop through, you're moving the reference point of your three different pointers (next, prev, current) forward.
Final solution
reverse(){
let current = this.head
this.head = this.tail
this.tail = this.head
let next = current.next
let prev = null
let counter = 0
while (counter < this.length){
// bump up next node
next = current.next
// bump up previous node
current.next = prev
prev = current
// bump up current node
current = next
counter++
}
return this
}
You can see the whole solution (including the classes) here.
I hope this is helpful. As someone who struggled with visualizing the exact operations for while, I really hope it does. But as someone who admittedly struggled, this may very much be a case of the blind leading the blind.
Yesterday, my solution to this problem was different and it may be different again tomorrow. This video by Quinston Pimenta was a huge help in this finally clicking. So I highly recommend watching it a few times as I did.
Also, check out this article from freeCodeCamp.
If you have an even better solution, let me know in the comments
Top comments (0)