java - 了解如何反转链表？

Question

这个问题已经有答案了:

How can I reverse a linked list? (13 个回答)

已关闭 9 年前。

我有以下用于反转链接列表的代码:

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

旧=临时；

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

旧=临时；

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

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

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