我有逆转的链接列表下面的代码:了解如何反转链接列表?
node old = head;
head = null;
while (old!=null) {
node temp = old.link;
old.link = head;
head = old;
old = temp;
}
能有人请解释这段代码的每一行,因为我想看到抽出方框图,如何逆转列表中,但我仍不很不明白。
我有逆转的链接列表下面的代码:了解如何反转链接列表?
node old = head;
head = null;
while (old!=null) {
node temp = old.link;
old.link = head;
head = old;
old = temp;
}
能有人请解释这段代码的每一行,因为我想看到抽出方框图,如何逆转列表中,但我仍不很不明白。
假设head
是一个指针到一个列表(1,2,3,4)的头部:
+-----+ link +-----+ link +-----+ link +-----+ link
| 1 | ---> | 2 | ---> | 3 | ---> | 4 | ---> null
+-----+ +-----+ +-----+ +-----+
^ head
节点旧=头;
head = null;
+-----+ 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
head = old;
+-----+ 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
(第二次迭代...)
节点温度= 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
head = old;
+-----+ 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
点到末尾空(即,直到原来的列表为空)。
它有助于在绘制每一行代码
希望你可以关注该发生什么,我号的每一行代码到循环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;
}
编辑:Woops它切割底部图一点点。 Head应该指向新的第一个节点(图中的最后一个节点)。 Temp和Old应该都是空的。而以前的第一个节点现在指向Null,因为它现在是最后一个节点。因此它被成功逆转。
可能比我正在研究的ascii艺术怪物更好。 – Kevin
哈哈我花了一段时间试图找出如何绘制它,然后我想起了什么笔和纸! –
+-----+ +-----+ +-----+
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!
这个问题可能会得到关闭,但如果你真的需要绘制盒的麻烦(拍照),并要求在一个specifc问题,你将有一个响应的更好的机会,你可以从中学到东西。 –
让我们假设你有一个'35 - > 42 - > 7 - > 80'的列表,现在你可以计算循环中的变量会发生什么吗? –
绘制更多图表。或者,最好在每次迭代后写出每个变量的状态,包括与什么相关的内容。从4-5个元素的列表开始。 –