算法学习-玩转单链表反转

说两句

单链表是一种基本的数据结构,也是现在技术面试经常考到东西(我曾在这跌倒过,那叫个惨,谁让我们平时并不注重这些基本算法呢),所以呢,身为技术人员,还是要多看看这些数据算法,万一哪天我们都成为大神呢,哈哈哈!

单链表反转

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. 三指针循环法
关键点:

1. 解决循环反转过程中断链问题
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;

    }

可以看出两个方法,递归法会出现两个节点指向同一节点情况,三指针法会出现断链情况.比较而言,递归法更简洁.