Как работает замена узлов в связанном списке? - PullRequest
Новая
       34

Как работает замена узлов в связанном списке?

2 голосов
/ 01 июня 2019

Ниже приведен код для замены узлов без изменения данных. Интересно, требуется ли замена следующих указателей узлов? Поменяет ли местами текущие узлы следующие указатели? Почему? 

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

Спасибо.

Ответы [ 2 ]

4 голосов
/ 01 июня 2019

требуется ли замена следующих указателей узлов?

Да, это необходимо, поскольку исходные узлы располагаются в разных позициях списка.

Поменяет ли местами текущий обмен следующие указатели?

Да, поменять текущие узлы не поменяет местами следующие указатели.Замена текущих узлов означает только замену только указателей, которые указывают на текущие узлы.

Рассмотрим, например, список 

| 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 "указывает" на 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|
2 голосов
/ 01 июня 2019

Замена текущих узлов будет недостаточной.

При переключении a и b их адрес изменяется, поэтому их место в списке будет заменено

Но вы не меняете внутренние поля каждого узла.

Узлы Illustraion:

a - b - c - d

Давайте возьмем узлы а и с.

a-> next == & b (True)

c-> next == & d (True)

Если мы поменяем узлы следующим образом:

с - б - а - д

Адрес узла c и узла a изменится, но список будет выглядеть так же, так как их -> следующие значения не изменятся

Если мы также поменяем местами значения -> next, список действительно поменяется местами

...