美文网首页
从尾到头打印链表

从尾到头打印链表

作者: Rarestzhou | 来源:发表于2018-09-08 09:32 被阅读0次

    题目:输入一个链表的头节点,从尾到头反过来打印出每个节点的值


    解决方法:

    1. 使用 栈 (后进先出) ,遍历链表(从头到尾),输出是从尾到头
    2. 递归 (递归的本质也是一个栈结构)
    3. 头插法 (链表头插法为逆序)

    代码实现:

    /**
     * 题目类型:链表
     *
     * 题目要求:输入一个链表的头节点,从尾到头反过来打印出每个节点的值
     *
     *思路:1. 遍历链表(从头到尾),输出是从尾到头,因此使用 栈 (后进先出)
     *
     * 2. 递归 (递归的本质也是一个栈结构)
     *
     * 3. 链表头插法(逆序)
     */
    public class PrintLinkedList {
    
        public static class ListNode {
    
            private int value; // 节点的值
    
            private ListNode next;  // 下一个节点
        }
    
        /**
         * 方式 1 :使用栈的方式
         *
         * @param root 头节点
         */
        public static void printListFromTailToHead(ListNode root) {
            Stack<ListNode> stack = new Stack<>();
            while (root != null) {
                stack.push(root);
                root = root.next;
            }
    
            ListNode temp;
            while (!stack.isEmpty()) {
                temp = stack.pop();
                System.out.print(temp.value + " ");
            }
        }
    
        /**
         * 方式 2 :递归
         *
         * @param root
         */
        public static void printListByRecursion(ListNode root) {
            if (root != null) {
                printListByRecursion(root.next);
                System.out.print(root.value + " ");
            }
        }
    
        /**
         * 方式 3 :头插法 (链表头插法为逆序) 尾插法为顺序
         *
         * 头节点和第一个节点的区别:
         *      1. 头节点是在头插法中使用的一个额外节点,该节点不存储值
         *      2. 第一个节点就是链表第一个真正存储值的节点
         *
         *时间复杂度:每个节点插入的时间为 O(1),设单链表长为 n,则 T(n) = O(n )
         *
         * @param root 原链表的头节点
         */
        public static void printListByHeadInsertion(ListNode root) {
            // 头插法构建逆序链表(新的链表的头节点)
            ListNode head = new ListNode();
            while (root != null) {
                ListNode listNode = root.next; // listNode指向原链表的第二个节点
                root.next = head.next; // 断开原链表头节点与其下一节点的连接
                head.next = root; // 新链表的头结点的下一节点指向原链表的头节点
                root = listNode;// 相当于 root = root.next
            }
    
            // 构建ArrayList
            ArrayList<Integer> ret = new ArrayList<>();
            head = head.next;
            while (head != null) {
                ret.add(head.value);
                head = head.next;
            }
    
            for (int nodeValue : ret) {
                System.out.print(nodeValue + " ");
            }
        }
    
    
        public static void main(String[] args) {
            ListNode root = new ListNode();
            root.value = 1;
    
            root.next = new ListNode();
            root.next.value = 2;
    
            root.next.next = new ListNode();
            root.next.next.value = 3;
    
            root.next.next.next = new ListNode();
            root.next.next.next.value = 4;
    
            root.next.next.next.next = new ListNode();
            root.next.next.next.next.value = 5;
    
            System.out.print("栈的方式:");
            printListFromTailToHead(root);
            System.out.println();
            System.out.println();
            System.out.print("递归(本质也是栈)的方式:");
            printListByRecursion(root);
            System.out.println();
            System.out.println();
            System.out.print("头插法的方式:");
            printListByHeadInsertion(root);
        }
    }
    

    相关文章

      网友评论

          本文标题:从尾到头打印链表

          本文链接:https://www.haomeiwen.com/subject/cndkgftx.html