c - 删除链表中间的节点

Question

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

#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 4 5。然后如果我输入 0 作为要删除的索引，程序将打印出 2 3 4 5。这无论我输入 0 还是 1 都有效。但是，当我输入索引 2 及以上时，它会给我奇怪的输出，例如，如果我将链接列表设置为 1 2 3 4 5，然后输入索引 2 以删除，按权利它应该输出 1 2 4 5，但它输出 2 4 5，我不知道发生了什么，请指出正确的方向。

Answer 1

在 deleteNode 中，您使用实际的头指针遍历列表。当您循环遍历列表时，您会移动实际的头部!您应该只在删除第一个元素时修改 (*ptrHead)。

我建议您将*ptrHead 复制到一个局部变量，并使用该局部变量遍历列表。

我用以 //*** 开头的注释突出显示了重要的行

int deleteNode(ListNode **ptrHead, int index)
{
    int count = 0;
    ListNode* temp1 = NULL;
    ListNode* temp2 = NULL;
    ListNode* traverse = *ptrHead;   // *** make a copy that we can use to traverse the list
    while (count <= index)
    {
        if (index == 0)
        {
            temp2 = (*ptrHead)->next;
            free((*ptrHead));
            (*ptrHead) = temp2;  // *** Keep this line as it is to correctly handle deletion of index 0.
            return 0;
            break;
        }
        if (count+1 == index)//checking for the node ahead
        {
            temp1 = traverse;                           // *** Use local copy of pointer
            temp2 = traverse->next;//the one to free    // *** Use local copy of pointer
            temp1->next = temp2->next;
            free(temp2);
            return 0;
            break;
        }
        traverse = traverse->next;                         // *** Use local copy of pointer
        count++;
    }
    return -1;
}