CoDEVIANT #25 — Linked List Surgery

What’s a matter, Red? You scared??
  • Takes the head of a Singly Linked list
  • Takes an integer k
  • Removes the kth node from the end of the Linked List
  • 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.
  • 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.
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.
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 = 0
while(clipCounter < number ) {
if(node.next && node.next != null) {
if(clipCounter == number - 1 ) {
node.next = node.next.next
}
clipCounter++
}
node = node.next
}
}
let counter = 1class LinkedList {
constructor(value) {
this.value = value;
this.next = null;
}
}
let counter = 1
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
}
}
  • 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.
function processNode(node, number) {
if(node.next != null) {
counter = number + 1
processNode(node.next, counter)
}
}
  • 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.
let calculatedNumber = counter - k
if(calculatedNumber != 0) {
clipTreeLinks(head, calculatedNumber)
} else {
head.value = head.next.value
head.next = head.next.next

}
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
if(clipCounter == number - 1 ) {
node.next = node.next.next
}
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
}
while(counter <= k) {
second = second.next
counter += 1
}
if second == null {
head.value = head.next.value
head.next = head.next.next
return
}
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

--

--

--

is a web developer, opera singer, actor, and lover of cats. (adrian-rosales.tech)

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Why is the malloc function giving more than the allocated space?

Get URL Parts in PHP — Web Dev Quick Tips

Relationship between SYSALIGN and the Metaverse

Top 10 Mistakes that Django Developers Make

Upgrading A Unity Project To URP

Observer Pattern

Top Programming Languages Based on industrial demands

Recommendation System with Association Rule Learning

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Adrian Rosales

Adrian Rosales

is a web developer, opera singer, actor, and lover of cats. (adrian-rosales.tech)

More from Medium

How Your Clothes are Made — Digital and Traditional Fashion

ArgoCD Best Practices You Should Know

Raccoon Malware Compromises in the Philippines Part 1

Blog 5 — L’approvisionnement et fidelite de Dieu