CoDEVIANT #25 — Linked List Surgery

So today, we’re going to put a linked list under a scalpel. Our job is to make sure we don’t fuck up the entire list while trying to get one little node out of there the correct way.

How I think I’ll approach this:

Althought it may end up more like this:

What’s a matter, Red? You scared??

Our mission is to write a function that:

• Takes the head of a Singly Linked list
• Takes an integer k
• Removes the kth node from the end of the Linked List

SPECIAL DIRECTIONS:

• If the head of the linked list turns out to be the one we’re supposed to remove, we simply update its value and next-pointer.

A quick word on linked lists. It’s an alternative datastructure to an array. Arrays are groups of bytes of data that are contiguously located in memory. Each element of the array is has its start positioned immediately after the end of the preceding element. There is no daylight between where one element ends and the next element starts.

Conversely, a linked list is made of nodes. Nodes have two parts:

• the byte(s) of memory that holds the node’s value, and
• the byte(s) of memory pointing to the address of the chunk that is the start of the next node.

The second part of a linked list node points to the address for the next node’s value portion.

In the crudely photoshopped image above, you can pretend the chess-board is the working memory of a computer. The portion in the white squares of the black-outlined groupings are the value-portions of the linked-list node. The darksquares adjacent to the value-portions are the pointers. Their value is a reference to the address of where the next value part of the next node is.

You can almost think of it like the lighting of the beacons…but for data. It’s a slight stretch, but if you have questions, ask away.

So here is the answer I came up with:

let counter = 1
class LinkedList {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}
function removeKthNodeFromEnd(head, k) {
  counter = 1
  processNode(head, 1)
  let calculatedNumber = counter - k
 
 if(calculatedNumber != 0) {
    clipTreeLinks(head, calculatedNumber)
 }  else {
  head.value = head.next.value
  head.next = head.next.next
 }
}
function processNode(node, number) {
 if(node.next != null) {
  counter = number + 1
  processNode(node.next, counter)
 } 
}
function clipTreeLinks(node, number) {
 let clipCounter = 0
while(clipCounter < number ) {
  if(node.next && node.next != null) {
   if(clipCounter == number - 1 ) {
    node.next = node.next.next
   }
  clipCounter++
  }
  node = node.next
 }
}

There’s alot going on here, so as always we are going to break it down step by step.

let counter = 1
class LinkedList {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

I create a globally scoped variable, it is editable and able to be referenced from any scope.

let counter = 1

Then I create the class of LinkedList. With the value argument used to instantiate an object based off the LinkedList class, the instance’s value (this.value) becomes whatever we pass into the constructor for value. The instance’s next property would be defined upon instantiation.

function removeKthNodeFromEnd(head, k) {
  counter = 1
  processNode(head, 1)
  let calculatedNumber = counter - k
 
 if(calculatedNumber != 0) {
    clipTreeLinks(head, calculatedNumber)
 }  else {
  head.value = head.next.value
  head.next = head.next.next
 }
}

Next, we create the method removeKthNodeFromEnd. Here’s what goes on line by line:

• We set counter, our global variable to 1 (in case it happens to not be 1 at the moment)
• We call the method processNode with the arguments of head and 1. It should be mentioned at this time that the code of processNode will impact what ‘counter’ is.
• Then we declare a variable called calculatedNumber that will be the difference of what counter is at that point and k.
• If calculatedNumber is not zero, which also means that we would not be trying to remove the head of the linked-list, then we call clipTreeLinks and pass in the head and the calculatedNumber.
• If calculatedNumber IS zero, however, we make the head’s value equal the following node’s value
• Also, if calculatedNumber IS zero, we make the head’s next value equal the following node’s next value.

So now we just need to know what’s going on in the processNode and clipTreeLinks methods. Let’s start with processNode!

function processNode(node, number) {
 if(node.next != null) {
  counter = number + 1
  processNode(node.next, counter)
 } 
}

Behold processNode. It takes the argument of a linked-list node (meaning it could be the head or some other part of the list), and a number.

• First, we look at the passed in node’s next value. If it is NOT null, then we make the global variable counter equal the passed in number plus 1. Afterwards, we call processNode on the current node’s next value and pass in our newly updated counter as the number-argument.
• So this will go on over and over until we reach the tail of the linked-list. The tail is the node in the linked list at the end where the next property is null, at which point, we enter the implicit else portion of the if-else statement where nothing happens.

The result of this sets up the global variable counter so that in the removeKthNodeFromEnd method, we can calculate the value of the variable calculatedNumber. By subtracting k from counter.

let calculatedNumber = counter - k

Now with that completed we come to a fork in the road. If calculatedNumber equals zero, this means that we are targeting the head of the linked-list. So we update the values of the head. head.value will become head.next.value and head.next will become head.next.next.

if(calculatedNumber != 0) {
    clipTreeLinks(head, calculatedNumber)
 }  else {
  head.value = head.next.value
  head.next = head.next.next
 }

In most cases, however, we will call the method clipTreeLinks passing in the head and the calculatedNumber variable which will be anything but zero.

function clipTreeLinks(node, number) {
 let clipCounter = 0
while(clipCounter < number ) {
  if(node.next && node.next != null) {
   if(clipCounter == number - 1 ) {
    node.next = node.next.next
   }
  clipCounter++
  }
  node = node.next
 }
}

• First we say that clipCounter is zero.
• We say that while clipCounter is less than the number argument that was passed in, if node.next exists, then in MOST cases, we will simply increment clipCounter by one and say the node is now the following node.
• However if clipCounter equals the number minus 1….THEN we say that node.next will be the subsequent node’s next

Basically how this works is the number is the 1-indexed length of the linked-list (1…2…3..4…etc). To remove a node from a singly-linked list, we need to change what the previous-Node’s .next value is. By doing this, we effectively cut a node out of the chain of pointers indicating the address of the next node. So it makes sense that we’re looking for the integer before number. So once we find that place in the list, we say that the next value of the node before the one we want to remove will now (instead of being node.next [leading to the one we want to get rid of]) be node.next.next.

if(clipCounter == number - 1 ) {
    node.next = node.next.next
}

And that’s literally it! We can sew the patient up and go about our day.

— — — — — — — — — — -

So what’s a better way of solving this? Apparently it’s this:

function removeKthNodeFromEnd(head, k) {
  let counter = 1
 let first = head
 let second = head
 
 while(counter <= k) {
  second = second.next
  counter += 1
 }
 if second == null {
  //this means the value we wanted to remove from a 10 lenth list is the 10th, which means the frist pointer (head)
  //is at the node that needs updating
   head.value = head.next.value
   head.next = head.next.next
  return
 }
 while(second.next != null) {
  second = second.next
  first = first.next
 }
 //once the second goes fast enough to get to null, 
 //then we know that first.next needs to be first.next.next
 first.next = first.next.next
}

So first we create a counter variable in the scope of the removeKthNodeFromEnd function then we create two variables that equal the head argument: first and second.

The idea with this solution is that we’re going to send out second before first. We will continuously make second equal second.next and increment counter by 1. We do this as long as counter is less than or equal to k.

while(counter <= k) {
  second = second.next
  counter += 1
 }

If second equals null after all of that, then it means that for a 10 length list the integer k was is 10, so our first doesn’t need to move at all. We just have to update head’s values.

if second == null {
   head.value = head.next.value
   head.next = head.next.next
  return
 }

However, if second.next does not equal null, then we say that second equals second.next and first equals first.next. By making our while-loop with the counter be inclusive of k, we set up our calculation to not have any “off by one” errors, so that once we say that second.next indeed equals null, then the first is in the position of the node before the one we want to get rid of. And in that case all we do is say that first.next equals first.next.next and that’s all there is!

first.next = first.next.next

Here’s a crude image of k being 3. Where we send ‘second’ out 3 spaces. and then once more so that second.next equals null. At which point first.next needs to become first.next.next