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

Question

我有两个循环双向链表与头和整数元素（无序）相连。想要删除的第一个列表包含第二个列表中的值。指针如何工作？如何进行排除？需要在第一个列表中搜索值以删除第二个列表？我如何与他们合作？能解释一下求解算法的运行吗？

示例：

我有两个带头的循环双向链表。

L1: 40 100 90 20 10 32 66

L2: 60 10 46 30 80 90

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

L1: 40 100 20 32 66

我想知道如何使用列表的指针来进行排除。我想要一个伪代码的概念。我已经创建了 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);

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

Delete in circular doubly linked list connected with head

c

circular-list

data-structures

doubly-linked-list