c - 如何在遍历单链表时删除任意节点？

Question

我有一个包含 x 个节点的单链表，其中一些节点是重复的。我需要在遍历列表时删除重复项，因此最终得到一个仅包含唯一节点的新列表。但是，我还需要计算所有重复项的平均值，以便唯一列表将包含这些平均值。

示例 1:假设我有一个这样的列表:a[1] -> b[2] -> c[3] -> a[2] -> a[3] -> b[2] -> null

遍历列表后，我应该得到这个列表:a[2] -> b[2] -> c[3] -> null

示例 2:假设我有一个这样的列表:a[2] -> a[2] -> a[5] -> b[2] -> b[4] -> c[3] -> null

遍历列表后，我应该得到这个列表:a[3] -> b[3] -> c[3] -> null

我认为我需要一种方法来删除重复的节点，因为我正在遍历列表，但我不知道如何删除。有人可以指导我如何实现这一目标吗？一些伪代码会很棒。谢谢。

编辑:解决了我的问题。详情请参阅答案...

Answer 1

我找到了解决问题的方法。只是为了分享将来是否有人遇到同样的问题。

回顾一下，问题如下:我有一个包含 x 个节点的单链表(x 是任意的)。每个节点有两个字段，即 id 和 value。在此列表中，某些节点是重复的，即它们具有相同的 id。每个 id 的重复次数也是任意的。我需要删除所有重复项，同时计算它们的平均值。最后，我应该得到一个仅包含唯一 id 节点(及其各自的平均值)的列表。唯一节点的数量也是任意的(事先未知)。

示例 1:之前:a[1] -> b[2] -> c[3] -> a[2] -> a[3] -> b[2] -> null。之后:a[2] -> b[2] -> c[3] -> null

示例 2:之前:a[2] -> a[2] -> b[6] -> b[2] -> b[4] -> null。之后:a[2] -> b[4] -> null

伪代码:

1. 将第一个 id 和值保存到变量中，即 id=head->id, val=head->val;
2. 如果列表不为空，即 head != null;
3. 将 head 分配给当前指针，将 head->next 分配给下一个指针，即 currPtr=head； nextPtr=头->下一个；
4. 当我们使用 next 指针遍历列表时，它不为空，即 nextPtr != null;

5. 将 nextPtr 指向的节点与 id 进行比较。

   如果相同，则将节点的值添加到 val 中，即 val += nextPtr->val。设置当前下一个指针指向下一个下一个指针，即 currPtr->next = nextPtr->next。免费的 nextPtr。然后设置下一个指针指向当前下一个指针，即 nextPtr = currPtr->next。

   否则，将当前指针设置为下一个指针，将下一个指针设置为下一个指针，即 currPtr=nextPtr； nextPtr=nextPtr->下一个；

6. 一旦列表被下一个指针完全遍历，则平均 val(如果需要，可以添加到新列表)。

7. 删除第一个节点，因此现在 head 指向旧列表中的下一个节点。
8. 重复步骤 2-7。

代码:

struct node {
    char id[32];
    int val;
    struct node *nextNode;
}; 

void deleteNode(struct node **startPtr) {
    struct node *currentPtr = *startPtr;

    *startPtr = currentPtr->nextNode;
    free(currentPtr);
}

.... //other functions

int main () {
    ...
    char id[32];
    int val, cnt;
    struct node *head = NULL, *currPtr, *nextPtr;

    .... //ask user to input the list 

    while (head!=NULL) {
        strcpy(id,head->id);
        val = head->val;
        cnt = 1;
        nextPtr = head->nextNode;
        currPtr = head;
        while (nextPtr != NULL) {
            if (strcmp(nextPtr->id,id)==0) {
                val += next->val;   
                cnt++;
                currPtr->nextNode = nextPtr->nextNode;
                free(nextPtr);
                nextPtr = currPtr->nextNode;
            } else {
                currPtr = nextPtr;
                nextPtr = nextPtr->nextNode;
            }
        }
        deleteNode(&head);
        printf("Node: %s, Value: %d\n",id,val/cnt); //or save into another list
    }

    .... //do other things
}