删除链表中间的节点 [英] deleting a node in the middle of a linked list

问题描述

我写了一段使用链表的代码.我让用户输入几个数字，然后要求用户输入他希望删除的数字的索引.我做了一些研究，发现我需要检查下一个节点是否是我要删除的节点，然后让2个临时指针指向当前节点和下一个节点(这是我要删除的节点)，然后将第一个临时指针的下一个节点分配给第二个临时指针的下一个节点，然后最终释放第二个临时指针.这是我的代码:

I have written a piece of code that uses linked lists. I get the user to enter a couple of numbers and then ask the user to enter the index of the digit he wishes to delete. I did some research and found out that i need to check whether the next node is the one I want to delete, then have 2 temp pointers point to the current node and the next node(which is the one i want to delete), then assign the next node of the first temp pointer to the next node of the second temp pointer then finally free the second temp pointer. Here is my code:

#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
    int item;
    struct node *next;
}ListNode;

void print(ListNode *head);
int deleteNode(ListNode **ptrHead, int index);

int main()
{
    int n;
    int remove;
    ListNode *head = NULL;
    ListNode *temp = NULL;
    printf("Enter a value: ");
    scanf("%d", &n);
    while (n != -1)
    {
        if (head == NULL)
        {
            head = malloc(sizeof(ListNode));
            temp = head;
        }
        else
        {
            temp->next = malloc(sizeof(ListNode));
            temp = temp->next;
        }
        temp->item = n;
        temp->next = NULL;
        printf("Enter a value: ");
        scanf("%d", &n);
    }

    printf("Enter index to remove: ");
    scanf("%i", &remove);

    while (remove != -1)
    {
        deleteNode(&head, remove);
        print(head);
        printf("Enter index to remove: ");
        scanf("%i", &remove);
    }
    while (head != NULL)
    {
        temp = head;
        head = head->next;
        free(temp);
    }
    head = NULL;
    return 0;
}
int deleteNode(ListNode **ptrHead, int index)
{
    int count = 0;
    ListNode* temp1 = NULL;
    ListNode* temp2 = NULL;
    while (count <= index)
    {
        if (index == 0)
        {
            temp2 = (*ptrHead)->next;
            free((*ptrHead));
            (*ptrHead) = temp2;
            return 0;
            break;
        }
        if (count+1 == index)//checking for the node ahead
        {
            temp1 = (*ptrHead);
            temp2 = (*ptrHead)->next;//the one to free
            temp1->next = temp2->next;
            free(temp2);
            return 0;
            break;
        }
        (*ptrHead) = (*ptrHead)->next;
        count++;
    }
    return -1;
}
void print(ListNode *head){
    if (head == NULL)
    {
        return;
    }
    while (head != NULL)
    {
        printf("%i\n", head->item);
        head = head->next;
    }
}

例如，如果我输入1 2 3 4 5 -1，则链接列表将包含1 2 3 45.然后，如果我输入0以删除索引，程序将输出2 3 45.这无论输入0还是1，都可以使用.但是，当我输入索引2和更高的索引时，它给我带来奇怪的输出，例如，如果我将链接列表设置为1 2 3 4 5，然后输入要删除的索引2(按权利)它应该输出1 2 4 5，但是输出2 4 5，我不知道发生了什么，请指向正确的方向.

So for example if i enter 1 2 3 4 5 -1, the linked list will contain 1 2 3 4 5. Then if i enter 0 for the index to remove, the program will print out 2 3 4 5. This works whether I enter 0 or 1. However, when I enter the indexes 2 and above, it gives me weird outputs like for example if I set the linked list as 1 2 3 4 5, and enter the index 2 to remove, by rights it should output 1 2 4 5, but instead it outputs 2 4 5, I have no idea whats going on, please point me in the right direction.

推荐答案

查找修改后的deleteNode函数(还处理边界条件，如果我们要删除的索引长度大于列表长度)

Find the modified deleteNode function (handles boundary conditions also , if we are trying to delete an index which is more then the list length)

int deleteNode(ListNode ** ptrHead，int index)

int deleteNode(ListNode **ptrHead, int index)

{

int count = 0;
ListNode* temp1 = NULL;
ListNode* temp2 = NULL;

temp1 = (*ptrHead);

while((temp1 != NULL) && (count <= index))
{
    if (index == 0)
    {
        temp2 = temp1->next;
        free(temp1);
        (*ptrHead) = temp2;
        return 0;
    }
    if ((count+1 == index) && (temp1->next != NULL))
    {
        ListNode*temp = NULL;

        temp = temp1->next;
        temp2 = temp->next;
        temp1->next = temp2;
        free(temp);
        return 0;
    }

    temp1 = temp1->next;
    count++;
}

return -1;

}

这篇关于删除链表中间的节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！