《剑指offer》05: 从尾到头打印链表

2021年11月25日 阅读数:4
这篇文章主要向大家介绍《剑指offer》05: 从尾到头打印链表,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。
❝
首先学习计算机科学及理论。接着造成本身编程的风格。而后把这一切都忘掉,尽管改程序就是了。—— 小浩

❞

从尾到头打印链表


题目描述

输入一个链表,按链表值从尾到头的顺序返回一个 ArrayList。java

原题题目

《剑指offer》05: 从尾到头打印链表

解法

解法一【推荐】
遍历链表,每一个链表结点值 push 进栈,最后将栈中元素依次 pop 到 list 中。git


/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
import java.util.Stack;

public class Solution {
    /**
     * 从尾到头打印链表
     * @param listNode 链表头节点
     * @return list
     */
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<>();
        if (listNode == null) {
            return res;
        }
        Stack<Integer> stack = new Stack<>();
        while (listNode != null) {
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        while (!stack.isEmpty()) {
            res.add(stack.pop());
        }

        return res;
    }
}

解法二【不推荐】
利用递归方式:github

若不是链表尾结点,继续递归;
如果,添加到 list 中。
这种方式不推荐,当递归层数过多时,容易发生 Stack Overflow。编程

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
import java.util.Stack;

/**
 * @author bingo
 * @since 2018/10/28
 */
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<>();
        if (listNode == null) {
            return res;
        }

        addElement(listNode, res);
        return res;

    }

    private void addElement(ListNode listNode, ArrayList<Integer> res) {
        if (listNode.next != null) {
            // 递归调用
            addElement(listNode.next, res);
        }
        res.add(listNode.val);
    }
}

思路扩展

《剑指offer》05: 从尾到头打印链表

测试用例

  1. 功能测试(输入的链表有多个结点;输入的链表只有一个结点);
  2. 特殊输入测试(输入的链表结点指针为空)。

    本题考点

    《剑指offer》05: 从尾到头打印链表
    我把我写的全部题解整理成了一本电子书放在了 github 上,三天内冲击到 github 排行榜榜首!近 5w 人下载阅读!要获取的话,直接进入下方连接就能够了(记得给我点个 star)markdown

https://github.com/geekxh/hello-algorithmide

《剑指offer》05: 从尾到头打印链表