问题
最近研究算法,遇到的一道很有意思的问题——怎么把一个链表反转?很容易想到一个方法:遍历链表,数组作栈存储路径,元素逐个出栈得到的就是反转后的链表!查找资料发现,有更好的方式实现。
仔细研究后,终于明白了其中的奥妙。小僧掌握了两种方法,以下分别进行说明。
首先给出链表结构:
public class LinkedNode {
Integer id ;
LinkedNode next;
public LinkedNode(Integer id) {
this.id = id;
}
}
下一步构造出上图的链表结构:
LinkedNode node1 = new LinkedNode(1);
LinkedNode node2 = new LinkedNode(2);
LinkedNode node3 = new LinkedNode(3);
LinkedNode node4 = new LinkedNode(4);
node1.next = node2;
node2.next = node3;
node3.next = node4;
双指针遍历法
先给出代码实现:
/**
* 链表翻转,循环 + 双指针(pre、next)实现
* @param cur
* @return
*/
public LinkedNode reverse(LinkedNode cur){
LinkedNode pre = null;
while (cur!=null){
LinkedNode next = cur.next; // 1.
cur.next = pre; // 2.
pre = cur; // 3.
cur = next; // 4.
}
return pre;
}
循环体之前,链表示意图:
之后进入 while 循环,注释标注的四个步骤会产生如下变化(图中编号与注释编号一一对应):
第一次循环后,链表变成这样:
之后的遍历,链表的变化示意:
可见,while 循环执行完,pre 指向的节点,已经是最新的头节点了!
递归法
递归的实现方式,似乎更容易理解。
/**
* 链表反转,递归实现
* @param node
* @return
*/
public LinkedNode reverse2(LinkedNode node){
if(node.next==null){
return node;
}
LinkedNode newHead = reverse2(node.next);
node.next.next = node; //node.next.next 换成 newHead.next 不行,因为 node 在递归中在追溯上一个节点,仔细体会下
node.next = null;
return newHead;
}
首先会通过递归调用找到尾节点,之后做了两件事:
尾节点反指 (node.next.next = node;)
当前节点指向 null 节点 (node.next = null;)
rentun newHead 后,回溯到节点 2(此时 node 就是节点 2),再次重复之前的两件事——节点反指和当前节点指向 null 节点。
再次回溯,得到最终的结果。
老规矩,完整代码见 git:暗夜君王的 demo 练习——链表反转
Done !