算法2:链表的逆转

时间:2022-11-19 12:14:20
  • 首先,我们以单链表为例子进行演示。总所周知,单链表的每个节点都会持有当前节点的下一个节点的对象引用,即next。现在的题目是:“设计一个算法,逆转一个已知的单链表”。解题思路是:单链表是有序的,即知道一个节点,那么我们就可以确认当前节点(node)的下一个节点(next),即node持有next对象引用。如果反过来,next持有node,那不就是逆转吗?
    package code.code_02;
    
    /**
     * 题目:设计一种算法,可以逆转单链表
     */
    public class SingleNodeList {
    
        //单链表
        private static class Node {
            public int data;
            public Node next;
    
            Node (int _data){
                this.data = _data;
            }
            public int getData() {
                return data;
            }
        }
    
        //循环的方式逆转
        public static Node reverseNode (Node node) {
            if (node == null) {
                System.out.println("链表不存在");
            }
            //标记前一个已经完成逆转的节点
            Node prev = null;
            //标记下一个待逆转的节点
            Node next = null;
    
            do {
                //步骤一
                //记录当前节点的下一个节点,因为它是下一个待逆转的节点。
                //如果不标记,执行步骤二会导致可达性分析无法完成,导致第一个节点完成逆转后剩余节点被内存回收
                next = node.next;
    
                //步骤二
                // 进行节点逆转操作
                //第一次进入,当前节点将会变成逆转后的最后一个节点。而最后一个节点的next将会指向null
                //再次进入的时候,因为第一次执行了步骤三,prev将会变成上一个已经完成逆转的节点,那么它自然变成当前节点逆转后的下一个节点
                node.next = prev;
    
                //步骤三
                //因为当前node已经逆转完成,把它标记并为下一个节点的后继节点做准备。
                //第二次进入的时候在步骤二中调用
                prev = node;
    
                //步骤四
                //此时的node引用移动到逆转前当前节点的下一个节点,next已经在步骤一中记录
                node = next;
            } while(node != null);
    
            //此处为什么要返回prev,而不是返回当前节点node呢?
            //因为最后一个节有值点为4, 而他的下一个节点为null. 我们需要的是链表中实际存在的节点
            return prev;
        }
    
        //递归的方式逆转链表
        public static Node reverseNode2 (Node curNode,  Node preReverseNode, Node next)
        {
            if (curNode == null) {
                return curNode;
            }
    
            curNode.next = preReverseNode;
            preReverseNode = curNode;
            curNode = next;
    
            //逆转后需要再次确认当前待逆转的节点是不是null,如果是null说明已经是逆转前的最后一个油值节点4的下一个节点了。
            // 那么我们只要返回最后一个有值节点即可,因为我们需要的是链表中实际存在的节点
            return curNode != null ? reverseNode2(curNode, preReverseNode, curNode.next) : preReverseNode;
        }
    
    
        public static void printNode (Node node) {
            if (node == null) {
                System.out.println("链表不存在");
            }
            System.out.println("当前链表的值为: " + node.getData());
            //递归的方式逐层打印Node的子节点
            if(node.next != null) {
                printNode(node.next);
            }
        }
    
        public static void main(String[] args) {
            //生成单链表
            Node n = new Node(1);
            n.next = new Node(2);
            n.next.next = new Node(3);
            n.next.next.next = new Node(4);
    
            System.out.println("打印循环逆转前的链表: ================================");
            printNode(n);
            n = reverseNode(n);
            System.out.println("打印循环逆转后的链表: ================================");
            printNode(n);
    
    
            Node n1 = new Node(1);
            n1.next = new Node(2);
            n1.next.next = new Node(3);
            n1.next.next.next = new Node(4);
    
            System.out.println("打印递归逆转前的链表: ================================");
            printNode(n1);
            n1 = reverseNode2(n1, null, n1.next);
            System.out.println("打印递归逆转后的链表: ================================");
            printNode(n1);
        }
    
    
    }

    打印结果为:

  • 打印循环逆转前的链表: ================================
    当前链表的值为: 1
    当前链表的值为: 2
    当前链表的值为: 3
    当前链表的值为: 4
    打印循环逆转后的链表: ================================
    当前链表的值为: 4
    当前链表的值为: 3
    当前链表的值为: 2
    当前链表的值为: 1
    打印递归逆转前的链表: ================================
    当前链表的值为: 1
    当前链表的值为: 2
    当前链表的值为: 3
    当前链表的值为: 4
    打印递归逆转后的链表: ================================
    当前链表的值为: 4
    当前链表的值为: 3
    当前链表的值为: 2
    当前链表的值为: 1
    
    Process finished with exit code 0

     

  • 既然是设计链表的逆转,当然是要区分单链表和双链表的。那么双链表又改如何设计呢?其实,原理一致,只不过双链表的每个节点会有一个last和next节点对象的引用而已。理解了单链表,那么改成双链表也就非常简单了
    package code.code_02;
    
    public class DoubleNodeList {
    
        //双链表
        private static class Node {
            public int data;
            public Node last;
            public Node next;
    
            Node (int _data){
                this.data = _data;
            }
            public int getData() {
                return data;
            }
        }
    
        public static Node reverseDoubleNodeList (Node node, Node prev)
        {
            if (node == null) {
                System.out.println("当前node节点为null");
                return node;
            }
            //记录当前节点的上一个节点,下一个节点,为逆转当前节点做准备
            //如果不记录,当前节点逆转后会导致数据丢失
            Node last = node.last;
            Node next = node.next;
    
            //逆转当前节点
            node.next = last;
            node.last = next;
            //prev记录当前已经完成逆转的节点,为下一次递归做准备
            //因为下一次递归的时候,我们需要记录最新的完成逆转的节点,而prev是为了记录已经完成逆转的节点
            prev = node;
            //完成逆转后, 当前节点node会移动到下一个节点
            node = next;
    
            //如果逆转前进入的节点是最后一个有值节点,那么你转完以后node会来到null的位置
            //此时,我们不需要对node==null的节点进行逆转,因此只需要返回最后一次完成逆转的节点即可
            //也许,prev会有歧义,我们可以换个合适的名称来代替prev, 比如preReversedNode
            return node != null ? reverseDoubleNodeList(node, prev):prev;
        }
    
        public static void printNode (Node node)
        {
            if (node == null) {
                System.out.println("链表不存在");
            }
            Node last = node.last;
            Node next = node.next;
            System.out.println("当前节点的值为: " + node.getData() + ", 上一个节点值为:" + (last != null ? last.getData():null) + ", 下一个节点为: " + (next !=null ? next.getData():null));
            //递归的方式逐层打印Node的子节点
            if(next != null) {
                printNode(next);
            }
        }
    
        public static void main(String[] args) {
            //构造出5个双链表节点
            Node node = new Node(0);
            Node node1 = new Node(1);
            Node node2 = new Node(2);
            Node node3 = new Node(3);
            Node node4 = new Node(4);
    
            node.next = node1;
            //node1节点
            node1.last = node;
            node1.next = node2;
            //node2节点
            node2.last = node1;
            node2.next = node3;
            //node3节点
            node3.last = node2;
            node3.next = node4;
            //node4节点
            node4.last = node3;
            System.out.println("逆转前node的hash值为" + node.hashCode());
            System.out.println("========================测试逆转前的双链表============");
            printNode(node);
    
            //此处为什么需要一个node来接受逆转后的值呢?
            //其实说是逆转,实际上是更新了内存中每一个对象的的值,并且更改了每一个node的指向。类似于生成了一个新对象
            //我们可以根据逆转前,逆转后的node的hash值进行确认
            //而实际开发中,如果只是一个object对象,比如set了一些变量值, 那么无法接受值(此处需要理解)
            node =reverseDoubleNodeList(node, null);
            System.out.println("逆转后node的hash值为" + node.hashCode());
            System.out.println("========================测试逆转后的双链表============");
            printNode(node);
        }
    }

    打印结果如下

    逆转前node的hash值为1163157884
    ========================测试逆转前的双链表============
    当前节点的值为: 0, 上一个节点值为:null, 下一个节点为: 1
    当前节点的值为: 1, 上一个节点值为:0, 下一个节点为: 2
    当前节点的值为: 2, 上一个节点值为:1, 下一个节点为: 3
    当前节点的值为: 3, 上一个节点值为:2, 下一个节点为: 4
    当前节点的值为: 4, 上一个节点值为:3, 下一个节点为: null
    逆转后node的hash值为1956725890
    ========================测试逆转后的双链表============
    当前节点的值为: 4, 上一个节点值为:null, 下一个节点为: 3
    当前节点的值为: 3, 上一个节点值为:4, 下一个节点为: 2
    当前节点的值为: 2, 上一个节点值为:3, 下一个节点为: 1
    当前节点的值为: 1, 上一个节点值为:2, 下一个节点为: 0
    当前节点的值为: 0, 上一个节点值为:1, 下一个节点为: null
    
    Process finished with exit code 0