# 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:

Our mission is to write a function that:

- Takes the head of a Singly Linked list
- Takes an integer
*k* - Removes the
*k*th 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.

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.

So here is the answer I came up with:

let counter = 1class 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 = 0while(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 = 1class 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 = 0while(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`