Remove elements from singly linked list (javascript)

Question

I'm doing a CodeFights problem, trying to remove elements from a singly linked list that has the value k.

Below is what I have (l is the list and k is the value):

function removeKFromList(l, k) {
    //figure out the head of the new list so we can reference it later
    var head = l;

    while (head.value === k){
        head = head.next;
    }

    var node = head;
    var temp = null;

    while (node && node !== null) {
        if (node.next.value === k){
            temp = node.next.next;
            node.next.next = null;
            node.next = temp;
        }
        node = node.next; 
        console.log("+++", head)
    }

    console.log("---", head)  
}

The CodeFight test cast is 3 -> 1 -> 2 -> 3 -> 4 -> 5. The final result would have been 1 -> 2 -> 4 -> 5. But my '---' console log keeps returning "Empty" (according to the CodeFights console).

My '+++' console log returns the correct head with element each loop.

I've been pulling my hair out over this, any idea what is missing here?

please add the example of the list es well, as the call of the function with values. — Nina Scholz
– Nina Scholz, Commented Dec 9, 2017 at 18:57
I included to test case. The list is already given as a SLL so I wouldn't have to create one. Hope this helps — Kaisin Li
– Kaisin Li, Commented Dec 9, 2017 at 19:12
one problem is the first node, you need to assign the next node as start of the list. this works only of the list is supplied via an object. — Nina Scholz
– Nina Scholz, Commented Dec 9, 2017 at 19:16
Your while loop condition should be while (node && node.next != null). — David G
– David G, Commented Dec 9, 2017 at 19:17

Nina Scholz · Accepted Answer · 2017-12-09 19:37:24Z

2

You need to return the list if you delete the first node.

Then you need a loop for taking the next not while the value is not found.

At last you need a check if the last node exist and if the value is found, then assign the next node to the last next property.

function removeNode(list, value) {
    var node = list,
        last;

    if (node && node.value === value) {
        return node.next;
    }

    while (node && node.value !== value) {
        last = node,
        node = node.next;
    }
    if (last && node.value === value) {
        last.next = node.next;
    }
    return list;
}

var list = { value: 1, next: { value: 2, next: { value: 3, next: { value: 4, next: { value: 5, next: { value: 6, next: { value: 7, next: null } } } } } } };

list = removeNode(list, 5);
console.log(list)

list = removeNode(list, 1);
console.log(list)

list = removeNode(list, 7);
console.log(list)

.as-console-wrapper { max-height: 100% !important; top: 0; }

edited Dec 9, 2017 at 19:37

answered Dec 9, 2017 at 19:29

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

lilRed Over a year ago

Could you explain why you returned the "list" as an output? I didn't see you use it anywhere; how is that work?

Nina Scholz Over a year ago

@FrogTuna, it is necessary if you remove the first node. if you take list without reassining, you keep the list. and if you move the asssigment into the function, you create a new object reference, but outside, you keep the one you have. please see edit for the difference.

lilRed Over a year ago

@ Nina Scholz, Sorry, I was trying to understand what u said and tested them by myself, but I still don't understand why the node is removed from the "list" when u only call "last.next = node.next;"? It seems like any changes in "last.next" will pass to the "list.next"? I could understand the first "if statement" and second "while statement", besides the last one

Nina Scholz Over a year ago

have you tried without?

lilRed Over a year ago

@ Nina Scholz, Sorry, I misunderstood the difference between value type and reference type, and now I understand exactly what you mean. Thank you.

Nilesh Kevlani · Accepted Answer · 2017-12-09 20:08:11Z

0

Try this:

function myRemove(l, k){
    if(l == null){
        return l;
    }
    while(l.value == k){
        l = l.next;
    }
    thisNode = l;
    nextNode = thisNode.next;
    while(nextNode != null){
        if(nextNode.value == k){
            thisNode.next = nextNode.next;
            // No more nodes, ie last node was to be removed
            if(thisNode.next == null)
                break;
        }
        thisNode = thisNode.next;
        nextNode = thisNode.next;       
    }
    return l;
}

answered Dec 9, 2017 at 20:08

Nilesh Kevlani

1,3361 gold badge10 silver badges11 bronze badges

Comments

Jonas Wilms · Accepted Answer · 2022-06-24 15:37:38Z

0

This could be also done by recursion:

 function removeKFromList({value, next}, k) {       
   if(value === k){
      return next ? removeKFromList(next, k) : null;
   } else {
      return {
        next : removeKFromList(next, k),
        value
       };
  }
 }

edited Jun 24, 2022 at 15:37

answered Dec 9, 2017 at 20:20

Jonas Wilms

139k20 gold badges164 silver badges164 bronze badges

1 Comment

Scott Sauyet Over a year ago

This is missing the second parameter from the second recursive call.

Vijaya Bhaskar Eswaran · Accepted Answer · 2023-03-16 01:24:35Z

Easy to understand solution :

remove(index) { 
if (index < 0 || index > this.length) return undefined 
if (index === 0) return this.shift() 
if (index === this.length - 1) return this.pop() 
let previousNode = this.get(index - 1) 
let removed = previousNode.next 
previousNode.next = removed.next 
previousNode.next = currentNode.next    
this.length-- 
return removed 
} 

get(index) { 
if (index < 0 || index >= this.length) return null 
let current = this.head 
let count = 0 
while (count !== index) { 
current = current.next 
count++ 
} 
return current 
} 

pop() { 
if (!this.head) return undefined 
let current = this.head 
let newTail = current
while (current.next) { 
newTail = current 
current = current.next 
} 
this.tail = newTail 
this.tail.next = null 
this.length-- 
if (this.length === 0) { 
this.head = null 
this.tail = null 
} 
return current 
} 
 

shift() { 
if (!this.head) return undefined 
let currentHead = this.head 
this.head = current.next 
this.length-- 
if (this.length === 0) { 
this.tail = null 
} 

return currentHead 

}

Collectives™ on Stack Overflow

Remove elements from singly linked list (javascript)

4 Answers 4

5 Comments

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

5 Comments

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related