Skip to content

Latest commit

 

History

History
156 lines (118 loc) · 5.92 KB

17.从尾到头打印链表.md

File metadata and controls

156 lines (118 loc) · 5.92 KB

目录介绍

  • 01.题目要求
  • 02.问题分析
  • 03.使用栈实现
  • 04.递归实现

好消息

  • 博客笔记大汇总【15年10月到至今】，包括Java基础及深入知识点，Android技术博客，Python学习笔记等等，还包括平时开发中遇到的bug汇总，当然也在工作之余收集了大量的面试题，长期更新维护并且修正，持续完善……开源的文件是markdown格式的！同时也开源了生活博客，从12年起，积累共计N篇[近100万字，陆续搬到网上]，转载请注明出处，谢谢！所有博客陆续更新到GitHub上！
  • 链接地址：https://github.com/yangchong211/YCBlogs
  • 如果觉得好，可以star一下，谢谢！当然也欢迎提出建议，万事起于忽微，量变引起质变！

01.题目要求

  • 输入链表的第一个节点，从尾到头反过来打印出每个结点的值。
    • image

02.问题分析

  • 对于这种颠倒顺序的问题，我们应该就会想到栈，后进先出。所以，这一题要么自己使用栈，要么让系统使用栈，也就是递归。注意链表为空的情况。时间复杂度为O（n）。
  • 注：不要想着先将单链表反转，然后遍历输出，这样会破坏链表的结构，不建议。

03.使用栈实现

  • 代码如下所示 
    public class LinkList {
    public Node head;
    public Node current;
    
    class Node {
        //注：此处的两个成员变量权限不能为private，因为private的权限是仅对本类访问。
        int data; //数据域
        Node next;//指针域
        public Node(int data) {
            this.data = data;
        }
    }
    
    //方法：向链表中添加数据
    public void add(int data) {
        //判断链表为空的时候
        if (head == null) {//如果头结点为空，说明这个链表还没有创建，那就把新的结点赋给头结点
            head = new Node(data);
            current = head;
        } else {
            //创建新的结点，放在当前节点的后面（把新的结点合链表进行关联）
            current.next = new Node(data);
            //把链表的当前索引向后移动一位
            current = current.next;   //此步操作完成之后，current结点指向新添加的那个结点
        }
    }
    
    
    //方法：从尾到头打印单链表
    public void reversePrint(Node head) {
        if (head == null) {
            return;
        }
        Stack<Node> stack = new Stack<Node>();  //新建一个栈
        Node current = head;
        //将链表的所有结点压栈
        while (current != null) {-
            stack.push(current);  //将当前结点压栈
            current = current.next;
        }

        //将栈中的结点打印输出即可
        while (stack.size() > 0) {
            System.out.println(stack.pop().data);  //出栈操作
        }
    }
}

04.递归实现

  • 代码如下所示
    • 基于递归实现的，看起来简洁优雅，但有个问题：当链表很长的时候，就会导致方法调用的层级很深，有可能造成栈溢出。而方法1的显式用栈，是基于循环实现的，代码的性能要更好一些。
    public class LinkList {
    public Node head;
    public Node current;
    
    class Node {
        //注：此处的两个成员变量权限不能为private，因为private的权限是仅对本类访问。
        int data; //数据域
        Node next;//指针域
        public Node(int data) {
            this.data = data;
        }
    }
    
    //方法：向链表中添加数据
    public void add(int data) {
        //判断链表为空的时候
        if (head == null) {//如果头结点为空，说明这个链表还没有创建，那就把新的结点赋给头结点
            head = new Node(data);
            current = head;
        } else {
            //创建新的结点，放在当前节点的后面（把新的结点合链表进行关联）
            current.next = new Node(data);
            //把链表的当前索引向后移动一位
            current = current.next;   //此步操作完成之后，current结点指向新添加的那个结点
        }
    }
    
    
    //方法：从尾到头打印单链表
    public void reversePrint(Node head) {
        if (head == null) {
            return;
        }
        reversePrint(head.next);
        System.out.println(head.data);
    }
}

其他内容

01.关于博客汇总链接

02.关于我的博客