what's wrong with my function to delete node from a circular linked list as some of the testcase are wrong

Question

Node* deleteNode(Node* head, int key) {
    if(head == NULL){
        return NULL;
    }
    //if their is only one node in list
    if(head -> data == key && head -> next == head){
        delete(head);
        head = NULL;
        return NULL;
    }
    
    // if first node is to be deleted
    Node* last = head;
    Node* temp = head;
    while(last -> next != temp){
        last = last -> next;
    }
    last -> next = temp -> next;
    delete(temp);
    head = last -> next;
    return head;
    

    while(last -> next != head || last -> next -> data != key){
        last = last -> next;
    }
    Node* dum = last -> next;
    last -> next = dum -> next;
    delete(dum);
    
    return head;
}

these are the test cases those are getting wrong

Test Case Input

1 2 3 4 5 -1
3

Your Output

2 3 4 5 -1

Desired Output

1 2 4 5 -1

one more is their that's wrong

Test Case Input

1 2 3 4 5 -1
6

Your Output

2 3 4 5 -1

Desired Output

1 2 3 4 5 -1

Look at the code that says `if first node is to be deleted`, then ask yourself where in that code do you check that the first node is to be deleted? This seems like a case of just seeing the code you have actually written instead of the code that you imagine you have written. — john, Sep 22 '22 at 07:17
Better than a debugger: grab a pencil and some paper and draw the lists as boxes and arrows, then trace through the code and update the drawings to see what you're doing. Start with the cases `1 2 -1 2` and `1 -1 2`. (It is a good idea to use the "drawing method" for solving the problem *before* you start writing code.) — molbdnilo, Sep 22 '22 at 07:30
[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — Jesper Juhl, Sep 22 '22 at 08:57

score 0 · Answer 1 · answered Sep 25 '22 at 16:17

your problem is so simple, you wrote :

// if first node is to be deleted
Node* last = head;
Node* temp = head;
while(last -> next != temp){
    last = last -> next;
}
last -> next = temp -> next;
delete(temp);

without the if condition that checks the condition called if first node is to be deleted, your code will always delete the first node for any key is entered even if it's not found as you didn't check for the condition if (head->data == key) but this isn't the case, also the logic of deleting a node in your linked list is incorrect, for the lines where you wrote:

while(last -> next != head || last -> next -> data != key){
    last = last -> next;
}
Node* dum = last -> next;
last -> next = dum -> next;
delete(dum);

this assumes that there is always a node to delete even if the node isn't found, your code will delete a node if the value you are searching for isn't found.

I modified your code and this is the edited code:

Node* deleteNode(Node* head, int key) {
    if (head == NULL) {
        return NULL;
    }
    //if there is only one node in the list
    if (head->data == key && head->next == head) {
        delete(head);
        head = NULL;
        return NULL;
    }

    Node* temp1 = head->next;
    Node* temp2 = head;

    // loop till find the node or return to the starting position
    do{
        // go to next node
        temp1 = temp1->next;
        temp2 = temp2->next;
    }while (temp1->data != key && temp1 != head->next);

    // we found the node to delete
    if (temp1 != head->next)
    {
        // remove that node from the linked list
        temp2->next = temp1->next;

        // if the node we are deleting is the head node
        if (temp1 == head)
        {
            // change the head as the node to delete is the head
            head = temp1->next;
        }

        // free that node memory
        delete(temp1);
    }
    
    return head;
}

since this is a circular linked list, deleting a node from the last is the same as deleting one from the middle and it's the same as deleting the head one but the only corner case is when you are deleting the head node, you should change the head node, that's why you will find this line in my code: if (temp1 == head)

I added some comments, thought might be helpful, also in my code, the temp1 pointer is the ahead pointer that is used to detect the node we are searching for and the temp2 pointer is the one used in deletion, to avoid infinite loop if the node isn't found, I loop till temp1 come back to its starting position.

what's wrong with my function to delete node from a circular linked list as some of the testcase are wrong

1 Answers1