我有以下用于反转链表的代码：
node old = head;
head = null;
while (old!=null) {
node temp = old.link;
old.link = head;
head = old;
old = temp;
}
有人可以解释一下这段代码的每一行，因为我试图通过绘制方框图来了解这如何反转列表，但我仍然不明白。
问问题
691 次
3 回答
7
假设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...)
node temp = 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
(第二次迭代...)
node temp = 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
重复 tilold指向最后的 null（即直到原始列表为空）。
于 2013-10-29T22:27:47.727 回答
4
+-----+ +-----+ +-----+
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!
于 2013-10-29T22:37:55.343 回答
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 应该指向新的第一个节点（图中的最后一个节点）。Temp 和 Old 都应该为 Null。并且曾经是第一个的 Node 现在指向 Null，因为它现在是最后一个 Node。因此成功逆转。
于 2013-10-29T22:07:31.780 回答