之前遇到反转链表的算法，比较晦涩难解，但其实挺简单的。
目标：将一个顺序链表反转。
思路：用三个辅助节点，每次实现一个节点的指向反转，即他的后继变为他的前驱。
三个辅助节点： p q r 按顺序分别指向 节点0,1,2， 然后一次次移动，指向1,2,3 ； 2,3,4......
算法分为三部分：
第一部分：初始化部分：
q是中心节点，是每次反转的节点，于是q是由函数参数传入的，前面的节点p一个是null，后面的节点r是q的后继节点q.next
第二部分：循环部分
分为两个操作：
1.反转：q的后继变为他的前驱: q.next = p
2.移动：pqr向后移动一位：
p = q; q = r;
r = r.next;
第三部分：尾部处理：
反转最后一个节点，并返回
public Node inverse(Node q) {//q初始化为头结点:一开始是： p=null，q=head r = head.next
//参考：https://blog.csdn.net/feliciafay/article/details/6841115
if (q == null) return null;//头结点为null，退出
/**
* 初始化部分：p=null，q=head(由函数参数传入) r = q.next
*/
// 一开始是： p=null，q=head r = head.next
Node r = q.next; //r是记录还有多少个节点，即p q r,如果r=null，表示后面已经没有更多的节点了，初始化为第二个
Node p = null; //初始化为null
/**
* 循环部分： q反转 + pqr整体移动。
*/
while (r != null) { //当当前节点有后继节点时
//反转节点q. (注意：q 是中心节点)
q.next = p;//q的后继节点指向他的父节点p
//p,q,r相继往后移动
p = q; //p后移动一个节点，即指向后继q
q = r; //q也往后移动一个节点，指向后继r
r = r.next;//r移动到下一个节点
}
/**
* 尾部处理部分：q反转
*/
q.next = p;//由于r到了最后节点的空子节点后，p,q还未反转，故将其反转
return q;//返回新的头结点，即原来的尾节点
}
//节点类
static class Node {//
Node next;
int data; Node(int data) {
this.data = data;
}
}
2018-12-11 13:24:26 DuXia Library XT