了解如何反向链接列表？

Question

我有以下代码来反转链接列表：

node old = head;
head = null;

while (old!=null) {
   node temp = old.link;
   old.link = head;
   head = old;
   old = temp;
}

请有人解释一下这段代码的每一行，因为我正在试图通过绘制方框图来了解这是如何逆转列表的，但我仍然不明白。

Answer 1

假设head是指向列表(1、2、3、4)的指针：

+-----+ link +-----+ link +-----+ link +-----+ link
|  1  | ---> |  2  | ---> |  3  | ---> |  4  | ---> null
+-----+      +-----+      +-----+      +-----+
 ^ head

节点老=头；

头=空；

+-----+ link +-----+ link +-----+ link +-----+ link
|  1  | ---> |  2  | ---> |  3  | ---> |  4  | --->  null
+-----+      +-----+      +-----+      +-----+
 ^ old

                                                     null

                                                      ^ head

( while循环的第一次迭代)

节点温度= old.link；

+-----+ link +-----+ link +-----+ link +-----+ link
|  1  | ---> |  2  | ---> |  3  | ---> |  4  | --->  null
+-----+      +-----+      +-----+      +-----+
 ^ old        ^ temp

                                                     null

                                                     ^ head

old.link =头；

+-----+ link +-----+ link +-----+ link +-----+ link
|  1  | -+   |  2  | ---> |  3  | ---> |  4  | --->  null
+-----+  |   +-----+      +-----+      +-----+
 ^ old   |    ^ temp
         |                            
         +---------------------------------------->  null

                                                     ^ head

头=旧；

+-----+ link +-----+ link +-----+ link +-----+ link
|  1  | -+   |  2  | ---> |  3  | ---> |  4  | --->  null
+-----+  |   +-----+      +-----+      +-----+
 ^ old   |    ^ temp
 ^ head  |                             
         +---------------------------------------->  null

老=临时；

             +-----+ link +-----+ link +-----+ link
             |  2  | ---> |  3  | ---> |  4  | --->  null
             +-----+      +-----+      +-----+
              ^ old
              ^ temp                   +-----+
                                       |  1  | --->  null
                                       +-----+
                                        ^ head

(第二次迭代)

节点温度= old.link；

             +-----+ link +-----+ link +-----+ link
             |  2  | ---> |  3  | ---> |  4  | --->  null
             +-----+      +-----+      +-----+
              ^ old        ^ temp
                                       +-----+ link
                                       |  1  | --->  null
                                       +-----+
                                        ^ head

old.link =头；

             +-----+ link +-----+ link +-----+ link
             |  2  | -+   |  3  | ---> |  4  | --->  null
             +-----+  |   +-----+      +-----+
              ^ old   |    ^ temp
                      |                +-----+ link
                      +--------------> |  1  | --->  null
                                       +-----+
                                        ^ head

头=旧；

             +-----+ link +-----+ link +-----+ link
             |  2  | -+   |  3  | ---> |  4  | --->  null
             +-----+  |   +-----+      +-----+
              ^ old   |    ^ temp
              ^ head  |                +-----+ link
                      +--------------> |  1  | --->  null
                                       +-----+

老=临时；

                          +-----+ link +-----+ link
                          |  3  | ---> |  4  | --->  null
                          +-----+      +-----+
                           ^ old
                           ^ temp

                          +-----+ link +-----+ link
                          |  2  | ---> |  1  | --->  null
                          +-----+      +-----+
                           ^ head

重复直到old指向末尾的null (也就是说，直到原始列表为空)。

Answer 2

       +-----+   +-----+   +-----+
head-->|     |-->|     |-->|     |-->null
       |  A  |   |  B  |   |  C  |
       |     |   |     |   |     |
       +-----+   +-----+   +-----+


node old = head
       +-----+   +-----+   +-----+
head-->|     |-->|     |-->|     |-->null
       |  A  |   |  B  |   |  C  |
       |     |   |     |   |     |
       +-----+   +-----+   +-----+
         ^^^
         old

head = null
       +-----+   +-----+   +-----+
head   |     |-->|     |-->|     |-->null
vvvv   |  A  |   |  B  |   |  C  |
null   |     |   |     |   |     |
       +-----+   +-----+   +-----+
         ^^^      ^^^^
         old      temp


node temp = old.link
       +-----+   +-----+   +-----+
head   |     |-->|     |-->|     |-->null
vvvv   |  A  |   |  B  |   |  C  |
null   |     |   |     |   |     |
       +-----+   +-----+   +-----+
         ^^^      ^^^^
         old      temp

old.link = head
       +-----+   +-----+   +-----+
head   |     |   |     |-->|     |-->null
vvvv   |  A  |   |  B  |   |  C  |
null<--|     |   |     |   |     |
       +-----+   +-----+   +-----+
         ^^^      ^^^^
         old      temp

head = old
       +-----+   +-----+   +-----+
head-->|     |   |     |-->|     |-->null
       |  A  |   |  B  |   |  C  |
null<--|     |   |     |   |     |
       +-----+   +-----+   +-----+
         ^^^      ^^^^
         old      temp

Rearranging slightly
old = temp
       +-----+
       |     |
       |  A  |
head-->|     |-->null
       +-----+
       +-----+   +-----+
 old-->|     |-->|     |-->null
       |  B  |   |  C  |
       |     |   |     |
       +-----+   +-----+
        ^^^^
        temp
Note that A is now a valid (if short) linked list.


node temp = old.link
       +-----+
       |     |
       |  A  |
head-->|     |-->null
       +-----+
       +-----+   +-----+
 old-->|     |-->|     |-->null
       |  B  |   |  C  |
       |     |   |     |
       +-----+   +-----+
                  ^^^^
                  temp

old.link = head
       +-----+
       |     |
       |  A  |
head-->|     |-->null
       +-----+
          ^
          |
       +-----+   +-----+
 old-->|     |   |     |-->null
       |  B  |   |  C  |
       |     |   |     |
       +-----+   +-----+
                  ^^^^
                  temp

head = old
       +-----+
       |     |
       |  A  |
       |     |-->null
       +-----+
          ^
          |
       +-----+   +-----+
 old-->|     |   |     |-->null
       |  B  |   |  C  |
head-->|     |   |     |
       +-----+   +-----+
                  ^^^^
                  temp

Rearrange,
old = temp
       +-----+   +-----+
       |     |   |     |
       |  B  |   |  A  |
head-->|     |-->|     |-->null
       +-----+   +-----+


       +-----+
 old-->|     |-->null
       |  C  |
       |     |
       +-----+
        ^^^^
        temp
Guess what? The sub-list A-B is now a valid list B-A.

node temp = old.link
       +-----+   +-----+
       |     |   |     |
       |  B  |   |  A  |
head-->|     |-->|     |-->null
       +-----+   +-----+


       +-----+
 old-->|     |-->null
       |  C  |    ^
       |     |    |
       +-----+    |
                  |
                 temp

old.link = head;
       +-----+   +-----+
       |     |   |     |
       |  B  |   |  A  |
head-->|     |-->|     |-->null
       +-----+   +-----+
          ^
          |
       +-----+
 old-->|     |-->null
       |  C  |    ^
       |     |    |
       +-----+    |
                  |
                 temp

head = old;
       +-----+   +-----+
       |     |   |     |
       |  B  |   |  A  |
       |     |-->|     |-->null
       +-----+   +-----+
          ^
          |
       +-----+
 old-->|     |   null
       |  C  |    ^
head-->|     |    |
       +-----+    |
                  |
                 temp

old = temp;
       +-----+   +-----+   +-----+
       |     |   |     |   |     |
       |  C  |   |  B  |   |  A  |
head-->|     |-->|     |-->|     |-->null
       +-----+   +-----+   +-----+

old-->null<--temp

Old is null, break out of the loop, we're done!

Answer 3

帮助绘制在每一行代码上发生的事情

希望您可以这样做，我将每一行代码编号到循环1-3，然后循环中的A、B、C、D如下：

1. Node old = head;
2. head = null;

3. while (old!=null) {
A.    Node temp = old.link;
B.    old.link = head;
C.    head = old;
D.    old = temp;
   }

​

​

编辑:喔，它剪了一些底部的图表。Head应该指向新的第一个节点(图中的最后一个节点)。临时和老应该都是空的。过去是第一个节点，现在指向Null，因为它现在是最后一个节点。因此，它被成功地逆转了。