单链表反转
单链表反转通俗表达：链上的后置指针全部倒戈。大家集体向后转，链头变链尾。
一道很基础但很考验对于链表掌握熟练度和细心程度的算法题。（代码量很适合用来白板书写）
先现思路
包含了两种实现思路，第一种就是把原来的链进行重新排序，依次移动链头和后续结点位置，实现反转（从图上看感觉有点像冒泡），另外一种实现就是用新链替换旧链。我自己实现了第一种；看答案发现答案的实现就是我考虑的第二种解法；）。
第一种实现
依次提升
手工版的第一次进行位置变动：
手画图：第一次“换头”
语言描述就是
每一次：
①原链的头结点指向新结点的后置结点；
②头结点被新结点后置指针指向；
③新结点成为头结点；
/**
* 单链表反转，依次转向
* @param head
*/
public static SingleLinkedList.Node reverse(SingleLinkedList.Node head) {
if (null == head || head.next == null) {
return head;
}
// 新的头结点
SingleLinkedList.Node newHead = null;
// 末尾节点
SingleLinkedList.Node lastNode = head;
SingleLinkedList.Node currentNode = head;
// 依次取链中数据
while (currentNode.next!=null){
if (null != newHead){
lastNode = newHead;
}
// 记录即将成为头结点的结点
newHead = head.next;
// 先拉住要动节点的后置节点，防止断链
currentNode.next = newHead.next;
// 新的头结点登基
newHead.next = lastNode;
}
return newHead;
}
/**
* 简化版
*/
public static SingleLinkedList.Node reverse2(SingleLinkedList.Node head) {
if (null == head || head.next == null) {
return head;
}
// 新的头结点
SingleLinkedList.Node newHead = null;
// 末尾节点
SingleLinkedList.Node lastNode = head;
// 依次取链中数据
while (head.next!=null){
// 记录即将成为头结点的结点
newHead = head.next;
// 先拉住要动节点的后置节点，防止断链
head.next = newHead.next;
// 新的头结点登基
newHead.next = lastNode;
lastNode = newHead;
}
return newHead;
}
第二种实现
依次获取结点，插入到新链中……
public static Node reverse5(Node head) {
Node curr = head, pre = null;
while (curr != null) {
// 老二准备
Node next = curr.next;
// 老老大就位
curr.next = pre;
// 新老大上位
pre = curr;
// 老二上位
curr = next;
}
return pre;
}
可能因为之前对算法研究较浅，有时候说不上来不同实现之间的本质区别，只能根据代码执行流程不同进行描述，甚至有时候觉得两种实现会很像。
比如我理解的单链表反转第二种实现：依次取出链中的结点，在新链进行头结点插入(链表的头插法)，就可以实现。如果仔细看上面的手画图，不难发现，新结点成为头结点不就是“头插法”吗？第一种实现中不执行标号为①的操作，就演变为了第二种实现！只是后面的代码用更少的指针实现（空间复杂度优）
根据代码，对比两种实现会发现：
- 第一种实现，每次循环结束链是没有断开的，依旧只有一条链；
- 第二种实现在循环中，会出现两条链，新链增长，老练变短，直至老链结点全部移到新链上。
总结
以上是我思考了若干天的总结，让我又一次体验到算法的神奇。关于第二种实现，上周日看了遍代码，只能隐约中可以在脑海中跑一遍代码。甚至有时候又不能复述出实现原理。在后面的两天里，我不时的回看这个算法，在脑海里反复的推演。最后是快把这个实现给“背“下来了，不能不能略显愚钝。
现在我的学习方法是，理解算法争取能在脑海里像玩积木一样，把这个处理流程给演义一遍
- 优点是形象生动，易于接受。
- 缺点：效率低；推理速度慢；每次都要像放电影一样，出错必须要从头再来。
目前我还未找到一条能躺着就学会数据结构和算法的道路，哈哈，只能正面刚了……
分享一个关于我总结出来记忆手写单链表反转的窍门（不喜轻喷）
回到前面第二个实现，我把实现过程用顺口溜的形式描述了下来。
历经几场风云变更：
1.【老二准备】理解为老队伍的老二待命，用一个临时变量（指针），标记老链表中第二个（next）结点。
2.【老老大就位】理解为老队伍的老大要准备上位了，怎么上位呢？骑到新队伍老大头上就可以了…，所以老的链头节点的后置结点改为指向新链的头结点。
3.【新老大上位】理解为就是接着上面的演，老队伍老大已经骑到新队伍前老大的头上了，但新老大的乌纱帽还没带上，带上新老大的官帽，大家就都认可他的地位了！所以新结点头结点为老头结点。
4.【老二上位】理解为现在老队伍的老大已经去当新队伍的头头了，老队伍里的已经待命的老二自然就当老队伍的的头头了，老链头结点点为标记的next结点。
结合代码，细细品味
public static Node reverse5(Node head) {
// pre:新链的头结点
Node curr = head, pre = null;
while (curr != null) {
// 老二准备：【老二准备】理解为老队伍的老二待命，用一个临时变量（指针），标记老链表中第二个（next）结点。
Node next = curr.next;
// 老老大就位： 【老老大就位】理解为老队伍的老大要准备上位了，怎么上位呢？骑到新队伍老大头上就可以了…，所以老的链头节点的后置结点改为指向新链的头结点。
curr.next = pre;
// 新老大上位：【新老大上位】理解为就是接着上面的演，老队伍老大已经骑到新队伍前老大的头上了，但新老大的乌纱帽还没带上，带上新老大的官帽，大家就都认可他的地位了！所以新结点头结点为老头结点。
pre = curr;
// 老二上位：【老二上位】理解为现在老队伍的老大已经去当新队伍的头头了，老队伍里的已经待命的老二自然就当老队伍的的头头了，老链头结点点为标记的next结点。
curr = next;
}
return pre;
}
网友评论