在与头部连接的双向链表中删除

Question

我有两个循环双链表，与head和integer元素（无序）相连。要删除的第一个列表中包含第二个列表中的值。你的工作怎么样？如何排除这种情况？需要搜索第一个列表中的值才能删除第二个列表？我怎样才能和他们合作？你能解释一下解决这个问题的算法吗？

例如：

我有两个循环的双链表，带有head。

L1:40100902003266

L2:60146308090

我想删除第一个列表中第二个列表中的值。第一个列表将是：

L1:40100266

我想知道如何使用列表的指针来进行这种排除。我想要伪代码中的一个概念。我已经用C语言创建了代码，但我不明白算法。我需要理解之前如何做。

Answer 1

从编写算法的伪代码开始，然后实现实际功能，可以独立测试。

一般的伪代码是这样的：

for each node in list1
{
    if (list2 contains node) 
    {
       remove node from list1
    }
}

假设列表和节点的定义如下：

struct Node 
{
    struct Node *next;
    struct Node *prev;
    int number;
}

struct List
{
    struct Node *head;
}

// these should be instantiated somewhere
struct List* list1;
struct List* list2;

所以，函数的骨架应该是这样的：

struct Node* node = list1->head;

while (node != null)
{
    // prepare the next node early
    struct Node* next = node->next;

    // check if list2 contains a matching node
    if (match(list2, node->number)) 
    {
        // remove the node properly,
        // updating whatever you need to update
        remove(list1, node);
    }

    // if it's circular, check if this
    // is the last node
    if (next == list1->head)
        break;

    node = next;
}

因此，现在只剩下实现两个函数：

// returns true if any node in list contains the specified number
bool match(struct List* list, int number);

// removes the node from the list
void remove(struct List* list, struct Node* node);