了解如何撤消链接列表？

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

node old = head;
head = null;

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

                                                     null

                                                      ^ head

(循环的第一次迭代while...)
node temp = old.link;

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

                                                     null

                                                     ^ head

old.link = head;

+-----+ 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

old = temp;

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

(第二次迭代......)
node temp = old.link;

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

old.link = head;

             +-----+ 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
                                       +-----+

old = temp;

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

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

old在结尾处重复倾斜点到空(即,直到原始列表为空).