图1

题: 如图1所示的链表结构, 写一个方法, 使用传入的节点将该链表反转 (传入的节点是首节点, 返回的节点是反转之后新的首节点)

解析:  反转链表的最终结果, 肯定是 5 -- 4 -- 3 -- 2 -- 1. 按照这个顺序, 我们可以这么想: 我们需要返回一个新的首节点(newHead), 那么不妨声明一个要返回的节点变量, 然后进行反转操作, 再将这个新的节点(newHead)返回回去, 就可以了.

但是反转的过程应该怎么做呢?

在这个题目中, 我们需要的结果是, newHead指向5, 5指向4, ... 直到1指向null. 但是我们所知道的, 也就是一个oldHead, 所以我们只能从oldHead出发, 依次拿到每一个节点指向的节点, 然后再串起来,

也就是说, 我们可以通过oldHead这个节点, 依次拿到它后面的所有节点, 然后在每一次拿到这个节点时, 将这个节点直接插入在newHead的后面, 同时, 将oldHead的next, 指向被拿走的这个节点的next. 

具体步骤如下:

第一步: 让newHead指向节点1, oldHead指向节点1的next, 节点1的next指向null. 因为反转之后, 节点1是最后一个了, 它的next就是null. 变成了图2-1.

图2-1

第二步: 在完成第一步后, oldHead这个节点就成了节点2. 此时让oldHead指向节点2的next也就是节点3, 让newHead指向节点2, 节点2的next再去指向节点1, 就变成了图2-2

图2-2

第三步: 重复这个交换步骤, 直到最后oldHead指向了null, 那么链表所有的节点都交换完了, 也就是反转完了, 变成了图2-3

图2-3

到此为止, 链表就反转完成

具体代码如下:

但是在整个交换流程中, 如果我们不使用一个临时变量去接收oldHead要指向的那个节点, 当我们改动了oldHead之后, 那个节点对于的线就断掉了, 从该节点以后的所有节点, 都会释放了. 

 循环到最后, oldHead指向了null, 结束. 链表成功反转, 新的首节点就是这个newHead.