交换链表中的节点如何工作？

Question

下面是在不改变数据的情况下交换节点的代码。我想知道是否需要交换节点的下一个指针？交换当前节点不会交换下一个指针吗？为什么？

    void swapNodes(Node** head_ref, int x, int y) 
    { 

        // Nothing to do if x and y are same 
        if (x == y) 
           return; 

        Node **a = NULL, **b = NULL; 

        // search for x and y in the linked list 
        // and store therir pointer in a and b 
        while (*head_ref) { 

              if ((*head_ref)->data == x) { 
                   a = head_ref; 
              } 

              else if ((*head_ref)->data == y) { 
                   b = head_ref; 
              } 

              head_ref = &((*head_ref)->next); 
         } 

         // if we have found both a and b 
         // in the linked list swap current 
         // pointer and next pointer of these 
         if (a && b) { 

             swap(*a, *b); 
             swap(((*a)->next), ((*b)->next)); 
         } 
    } 

    void swap(Node*& a, Node*& b) 
    { 

         Node* temp = a; 
         a = b; 
         b = temp; 
    }

谢谢。

Answer 1

交换当前节点是不够的。

当交换 a 和 b 时，它们的地址会改变，因此它们在列表中的位置将被替换

但是您不更改每个节点的内部字段。

节点插图：

a - b - c - d

让我们以节点a和c为例。

a->下一个 == &b（真）

c->下一个 == &d（真）

如果我们像这样交换节点：

c-b-a-d

节点 c 和节点 a 的地址会改变，但是列表看起来是一样的，因为它们的 ->next 值会不变

如果我们也交换 ->next 值，列表将真正交换

Answer 2

whether swapping the next pointers of nodes required?

是的，这是必需的，因为原始节点出现在列表的不同位置。

Will swapping the current nodes doesn't swap the next pointers?

是的，交换当前节点不会交换下一个指针。交换当前节点意味着只交换指向当前节点的指针。

以列表为例

| A |next B| -> | B |next C| -> | C |next D| -> | D |next nullptr|

假设您需要交换节点 B 和 D。那么您将得到

                   ---------------------
                   |                    |
| A |next D| ... | B |next C| -> | C |next B| ... | D |next nullptr|
       |                                            |
       ----------------------------------------------

所以在第一次交换节点 A 指向节点 D 但节点 D "points" 指向 nullptr 之后。如果下一步不交换它们的数据成员，节点 B 和 C 将丢失。

因此您接下来还需要交换它们的数据成员

                   --------------------------
                   |                        |
| A |next D| ... | B |next nullptr|   | C |next B| ... | D |next C|
       |                                                 |
       ---------------------------------------------------

结果你会得到

| A |next D| -> | D |next C| -> | C |next B| -> | B |next nullptr|

交换链表中的节点如何工作？

How does swapping nodes in linked list works?

c++

swap

linked-list

singly-linked-list