C:从单链表1中删除一个节点并将其插入到单链表2的头部

Question

我正在做一个模拟操作系统进程调度程序的计算机科学项目。我有多个单链表，需要在它们之间移动节点。我正在尝试编写一个通用的函数来完成此操作，但我认为我的使用指针的弱点阻碍了我。

如何实现所需的功能？到目前为止，我有以下内容:

typedef struct process_list_struct ProcessList;

struct process_list_struct
{
    Process proc;
    ProcessList* next;
};

void change_lists(ProcessList* node, ProcessList* newlist)
{
    ProcessList* temp = NULL;
    debug_printf("change_lists reached\n");
    temp = node;
    if(!node)
    {
        debug_printf("Error: change_lists failed!\n");
        return;
    }
    node = node->next;
    temp->next = newlist;
    newlist = temp;
    return;
}

结果很奇怪...我最终得到第一个列表，其中仅我想移动的节点，其他所有内容都丢失了(效果与我想要的)，新列表(测试为开始为空)仍然是空的。

我在单个列表中查看了节点交换的实现，并且看到人们使用双指针，但这真的让我感到困惑。有人可以告诉我如何在这种情况下应用它们吗？我尝试使用它们，但它们与结构的引用指针元素结合起来真的很困惑。

非常感谢帮助!

Answer 1

将节点从一个列表转移到另一个列表的四个步骤是错误的:

temp = node
node = node->next;
temp->next = newlist;
newlist = temp;

见下图:

假设您在链接的 list-1 中有节点:

    +---+----+----+      +----+----+----+      +---+----+----+
  ->|   zero      |----->|      one     |----->|    two      |--
    +---+----+----+      +----+----+----+      +---+---+-----+
                             ^   ^
                             |   |
                             |  node 
    after temp=node        temp

之后:node = node->next; 事情变成了这样:

    +---+----+----+      +----+----+----+      +---+----+----+
  ->|   zero      |----->|      one     |----->|    two      |--
    +---+----+----+      +----+----+----+      +---+---+-----+
                             ^                        ^
                             |                        |
                             temp                    node            

在 temp->next = newlist; 这之后？

    +---+----+----+      +----+----+----+      +---+----+----+
  ->|   zero      |----->|      one     |      |    two      |--
    +---+----+----+      +----+----+----+      +---+---+-----+
                             ^       |                ^
                             |       |                |
                             temp    |                node     
                                     |
                                     |
                                     |    "head node"
                                     |   +---+----+----+   +---+----+---+
         "This is your list-2"       |-->|   FIVE      |-->|   SIX      |--
                                         +---+---+-----+   +---+----+---+ 
                                          newlist

你的背阔肌 newlist = temp; ?

                           newlist                    
                            |
                            ▼ "head node"
    +---+----+----+      +----+----+----+      +---+----+----+
  ->|   zero      |----->|      one     |      |    two      |--
    +---+----+----+      +----+----+----+      +---+---+-----+
                             ^       |                ^
                             |       |                |
                             temp    |                node     
                                     |
                                     |    
                                     |   +---+----+----+   +---+----+---+
         "This is your list-2"       |-->|   FIVE      |-->|    SIX     |--
                                         +---+---+-----+   +---+----+---+

这就是您所做的。但这不是你想要的？
你将节点从一个列表转移到另一个列表的算法是错误的另外你犯了技术错误，你正在按值传递指针(你需要指针指向指针以反射(reflect)调用函数的变化)

因为你想将节点从一个列表转移到另一个列表，并传递一个列表中的 node 指针和另一个列表的头部，你需要传递指针的指针以反射(reflect)调用函数的变化，因此你的声明在我看来是错误的:

void change_lists(ProcessList* node, ProcessList* newlist)

我觉得应该是:

void change_lists(ProcessList** node, ProcessList** newlist) 

使用此原型(prototype)编写代码以移动节点。

编辑:(建议)

代码中的基本问题是，要移动列表 1 中的节点(例如一个)，您不会更改指向先前节点的指针(图中的零节点) , 你需要制作

[zero] ---> [two]

@CodeRat 在他的列表中犯了类似的错误:Swap nodes in a singly-linked list

我给了他一个我认为会帮助你实现代码的答案。

旧答案:

我能找到的一个错误:而不是

*temp = *node;

你应该写

temp = node;

地址不是值(value)观

做 *temp = *node; 是未定义的行为，因为你没有为 temp 分配内存，你需要在 temp 中分配地址。 (temp 指向 NULL)因为您想将节点从一个列表转移到另一个列表，这就是为什么您需要 temp = node;