Linked list removing elements issue

[tralsz]

So i am writing a code to remove an elements from linked list l that are equal to given k.

But for some reason i keep running into this issue where part of the linked list get lost.

assume this is l=[3,1,2,3,4,5]
k=3

// Definition for singly-linked list:
// template<typename T>
// struct ListNode {
//   ListNode(const T &v) : value(v), next(nullptr) {}
//   T value;
//   ListNode *next;
// };
//
ListNode<int> * removeKFromList(ListNode<int> * l, int k) {
    ListNode<int> *b=nullptr;

    ListNode<int> *h=l;
    b=h;
    ListNode<int> *last=l;
    ListNode<int> *temp=l;

    h=l;


    while(h!=nullptr){
        if(h->value==k){
            
            std::cout<<"foudn value"<<std::endl;      
            temp=l;
                while(temp!=nullptr){
                    std::cout<<"Value: "<<temp->value<<std::endl;
                    temp=temp->next;
                }
             
            if(h==l){
                std::cout<<"Found vale first node"<<std::endl;
                b=h->next;
                l=h->next;;
                h->next=nullptr;
                h=l;
                
            }
            else if(h->next=nullptr){
                
                std::cout<<"Found vale last node"<<std::endl;
                b->next=nullptr;
                h=b;
            }
            else{
                
                temp=l;
                while(temp!=nullptr){
                    std::cout<<"Value: "<<temp->value<<std::endl;
                    temp=temp->next;
                }
                std::cout<<"Found value mid node"<<std::endl;
                h=h->next;
                b->next=h;

                

                
                
                
            }
        }
        else{
            
            std::cout<<"Didn't Found"<<std::endl;
            b=h;
            h=h->next;

            

        }
    }


    return l;
}

Removing the first 3 isn't an issue.
But then when it find the next 3 it will print the list 12345.
Then before i change anything when it reach last else statement the list become 123. Nothing was changed at all. Maybe I missed something small. Please let me know.

[Peter87]

Line 38 is assigning nullptr to h->next. The compiler should be able to warn you about simple mistakes like this. With GCC you should at least use the -Wall compiler flag.

[tralsz]

Yeah it worked. Thank you very much. The code run an into an issue now that if that linked list is large. Any advise on that?

[keskiverto]

Lets assume root=[7,3,3,1,2,3,4,5]
and a call root->next = removeKFromList( root->next, 3 );
That should result: root=[7,1,2,4,5] ?

You have created the nodes somehow. Was it with new? If yes, then you have to delete.
Smart pointers would be a smart thing to use; saves errors.


Anyway, you do have two cases to consider:
1. The first node on list has k. Take it out.
2. It does not. Skip it.
Every node on the list is the first node of the rest of the list.

// remove the prefix matches
while ( l and l->value == k ) {
    auto dead = l;
    l = l->next;
    delete dead;
}
// handle the internal
if ( l ) {
  auto tmp = l;
  // skip
  while ( tmp->next and tmp->next->value != k ) {
    tmp = tmp->next;
  }
  tmp->next = removeKFromList( tmp->next, k );
}
return l;

If that code is correct, then we start with l=[3,3,1,2,3,4,5]
There will be two to erase and after them l=[1,2,3,4,5]
Therefore tmp=[1,2,3,4,5] and the skip progresses to tmp=[2,3,4,5]

Then we resort to recursion, although iteration would be just fine.
The second call starts with l2=[3,4,5]
Again, the erasure produces l2=[4,5] and skip until tmp2=[5]

The third call starts with l=[] and that is what it returns. The second call thus returns the [4,5]
to the first call that appends that to the [1,2] producing [1,2,4,5]

Now we are ready to return, and our caller will have their root=[7,1,2,4,5].