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

Question

Below is the code for swapping nodes without changing data. I wonder whether swapping the next pointers of nodes required? Will swapping the current nodes doesn't swap the next pointers? Why?

    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; 
    }

Thank You.

Answer 1

whether swapping the next pointers of nodes required?

Yes it is required because the original nodes take place in different positions of the list.

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

Yes, swapping current nodes doesn't swap the next pointers. Swapping current nodes means only swapping only pointers that point to the current nodes.

Consider for example the list

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

and let's assume that you need to swap nodes B and D. Then you'll get

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

So after the first swapping the node A points to node D but node D "points" to nullptr. Nodes B and C will be lost if not to swap their data members next.

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

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

结果你会得到

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