说两句
单链表是一种基本的数据结构,也是现在技术面试经常考到东西(我曾在这跌倒过,那叫个惨,谁让我们平时并不注重这些基本算法呢),所以呢,身为技术人员,还是要多看看这些数据算法,万一哪天我们都成为大神呢,哈哈哈!
单链表反转
1. 递归思想
递归思想,
重点问题一:在于找出递归退出点,显然单链表反转退出点在于尾节点的nex节点为null的判断上
重点问题二:递归过程中处理逻辑.递归思想每次处理的都是关联的两个元素,其实反转的重点思想在于将原有下级元素的next设置为它的父节点,而它的父节点会在递归的下次后将处理它的下一个节点的反转逻辑.
总结如下图,每次递归返回当前节点保存了它下一个节点的引用,然后反转本节点和下一个节点,本节点置为尾节点,以此类推:
递归反转单链表.png
核心代码如下:
public static Node reverser(Node root){
//1.跳出条件
if(root ==null||root.getNext()==null){
return node;
}
//2. 递归调用,直到最后节点
Node next=reverser(root.getNext());
//3. 递归每步进行逐步反转
root.getNext().setNext(root);
root.setNext(null);
//4. 返回新的尾节点
return next;
}
// 2. 三指针循环法
关键点:
- 解决循环反转过程中断链问题
- 三个指针后移,避免死循环问题
总结如下图,利用三个起始位置不同的指针,两个临时变量逐步后移,当出现断链时,通过第三个指针不断续接.
三指针反转.png
代码:
/**
* 循环进行反转
*/
public static Node reverser1(Node node) {
//空链表或只有一个节点，直接返回
if (node == null || node.getNext() == null) {
return node;
}
//三个指针，一个temp先走了两步，后续每次一步
//指针一，当前待反转节点，起步点为1
Node root=node;
//指针二，每次缓存当前节点的下一个节点，起步点为2
Node preNode=node.getNext();
//指针三，为待反转节点待下一个节点，用来解决反转后断链问题，起步点为3
Node temp = node.getNext().getNext();
//当前节点待下一个节点，用来缓存待反转的节点
if (temp == null) {
//链表长度为2，直接反转
node.getNext().setNext(node);
root=node.getNext();
node.setNext(null);
} else {
//链表长度大于2时
//跳出条件为快指针为null时，此时已经循环到链表最后两位
while (temp!=null) {
//通过指针二实现反转
preNode.setNext(root);
//当前节点后移一步
root=preNode;
//指针二后移一步
preNode=temp;
//指针三后移一步
temp=temp.getNext();
}
//最后两位处理，将最后两个节点进行反转
preNode.setNext(root);
root=preNode;
//把原链表首节点的下一个节点置为空
node.setNext(null);
}
return root;
}
可以看出两个方法,递归法会出现两个节点指向同一节点情况,三指针法会出现断链情况.比较而言,递归法更简洁.
