loading...

Pseudocode + how to reverse a linked list

jasterix profile image Jasterix ・3 min read

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 with null. This is because the tail is the last node and this.tail.next is always null.
  • Now, our head and tail nodes are just chilling out in the ether with no next references. this.head.next is also null.

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.
image of linked list 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

Posted on by:

jasterix profile

Jasterix

@jasterix

Passionate about building great technology and connecting with people to create positive change. Find me elsewhere @jasterix or @_jasterix

Discussion

markdown guide