剑指Offer面试题0(Java实现):从尾到头打印链表

时间:2020-9-2 作者:admin


剑指Offer:面试题06.从尾到头打印链表

目录

1.题目描述

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

2.解题思路

有两种解题思路:

  1. 因为遍历的顺序是从头到尾,可输出的顺序确实从尾到头。也就是说,第一个遍历到的结点最后一个输出,而最后一个遍历到的结点第一个输出。这就是典型的”后进先出”,我们可以使用栈来实现这种排序。每经过一个结点的时候,就把该结点放到一个栈中。当遍历完整个链表后,再从栈顶开始逐个速出结点的值,此时食醋胡的结点的顺序已经反转过来了。
  2. 使用递归实现,递归在本质上就是一个栈结构。

3.代码实现

使用栈:

	// 使用栈(先进后出)协助逆向遍历
    public void reverseTraversalLinkedList(Node temp){
        // 链表为空
        if(temp == null || temp.getNext() == null)
            return;

        Stack<Node> stack = new Stack<>();
        temp = temp.getNext();
        // 遍历链表,按照从头到尾的顺序将结点加到栈中
        while (temp != null){
            stack.push(temp);
            temp = temp.getNext();
        }

        // 先进后出原则,结点依次出栈并打印
        while(!stack.isEmpty()){
            System.out.println(stack.pop());
        }
    }

使用递归:

	// 使用递归实现逆向遍历
    public void reverseTraversalLinkedList1(Node temp){

        if(temp == null || temp.getNext() == null)
            return;

        // 因为传入的是头结点,所以需要从头结点的下一个结点开始
        if(temp.getNext() != null){
            // 结点的下一结点不为空
            if(temp.getNext().getNext() != null)
                // 递归下一结点
                reverseTraversalLinkedList1(temp.getNext());
            // 逆向打印
            System.out.println(temp.getNext());
        }
    }

4.测试用例(仅针对栈方式)

功能测试(输入的链表有多个结点,输入的链表只有一个结点)

public static void main(String[] args) {
        Node head = new Node(0);
        LinkedList linkedList = new LinkedList(head);
        for (int i = 1; i <= 5; i++) { // 输入的链表有多个结点
            linkedList.add(i);
        }
        linkedList.reverseTraversalLinkedList(head);
    }

剑指Offer面试题0(Java实现):从尾到头打印链表

public static void main(String[] args) {
        Node head = new Node(0);
        LinkedList linkedList = new LinkedList(head);
        linkedList.add(1); // 输入的链表只有一个结点
        linkedList.reverseTraversalLinkedList(head);
    }

剑指Offer面试题0(Java实现):从尾到头打印链表

特殊输入测试(输入的链表头结点指针为null)

public static void main(String[] args) {
        Node head = null;// 输入的链表头结点指针为null
        LinkedList linkedList = new LinkedList(head);
        linkedList.reverseTraversalLinkedList(head);
    }

剑指Offer面试题0(Java实现):从尾到头打印链表

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。