交换C中双链表中的节点

Question

我正在尝试交换 C 中双链表中的节点。

我的列表如下：M4,M3,M2,M1。我有一个计算列表维度的函数，它正确地将其读取为 4。

当我尝试将 M3 与 M2 交换时，一切都崩溃了。（希望遍历后得到：M4，M2，M3，M1。）

我在 main 中使用以下行：（prim 是第一个节点，M4）

swap_nodes1(prim->pNext, prim->pNext->pNext);

下面的代码作为我的交换功能。（注意：我仍然需要涵盖将头部切换到另一个节点或将尾部切换到另一个节点的情况，但我想先交换一些随机的中间位置节点。）

void swap_nodes1(pNODE object1, pNODE object2)
{
pNODE temp1,temp2;
temp1->pPrec=object1->pPrec;
temp1->pNext=object1->pNext;

object1->pPrec=object2->pPrec;
object1->pNext=object2->pNext;
object2->pPrec=temp1->pPrec;
object2->pNext=temp1->pNext;

free(temp1);
}

当我第二次遍历列表时，我得到：M4，M3，M1。此外，列表的 dim 现在是 3 而不是 4，M2 神奇地消失了。

任何人都可以向我解释为什么我会得到这个以及我做错了什么吗？

提前致谢。

Answer 1

如果你把它画在纸上并以这种方式进行研究，这会容易得多。

假设 object1 和 object2 不为 NULL。

您需要考虑要交换的两个节点之前和之后的节点。 before 你的两个交换节点现在需要指向 object2 而不是 object1（假设该节点存在）。并且您需要使 object2 的前导现在指向您的两个交换节点之前的节点。

if ( object1->pPrec != NULL )
   object1->pPrec->pNext = object2;
object2->pPrec = object1->pPrec;

并且您需要使 object1 的下一个指向节点 在您的两个交换节点之后 并且该节点需要指向回 object1（如果它存在）。

object1->pNext = object2->pNext;
if ( object2->pNext != NULL ) 
    object2->pNext->pPrec = object1;

那么object1需要指向object2，object2需要指向object1。

object1->pPrec = object2;
object2->pNext = object1;

Answer 2

问题陈述没有指定什么指向列表的第一个节点 (M4)，或者是否有指向列表的最后一个节点 (M1) 的指针。它没有说明列表是否是循环的，所以我假设它不是循环的。

交换列表中的节点时，如果要交换的节点相邻（例如，M3和M2），则指针需要"rotated"。如果要交换的节点不相邻，则需要交换指针。通过首先交换指向两个节点的内容，然后交换两个节点的指针，可以对这两种情况使用相同的逻辑。

使用指向节点指针的指针将简化逻辑。

交换C中双链表中的节点

Swapping nodes in double linked list in C

c

swap

nodes

doubly-linked-list