LCOF 06. 从尾到头打印链表

1. 问题

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

限制：

0 <= 链表长度 <= 10000

2. 解法1 - 栈

2.1 Java

class Solution {
    public int[] reversePrint(ListNode head) {
        Stack<Integer> stack = new Stack<Integer>();
        int len = 0;
        while (head!=null) {
             stack.push(head.val);
             head = head.next;
             len++;
        }
        int[] res = new int[len];
        int i = 0;

        while (!stack.empty()) {
            res[i] = stack.pop();
            i++;
        }

        return res;
    }
}

2.2 Kotlin

// 栈
class Solution {
    fun reversePrint(head: ListNode?): IntArray {
        var head = head
        val stack = Stack<Int>()
        var len = 0
        while (head != null) {
            stack.push(head!!.`val`)
            head = head!!.next
            len++
        }
        val res = IntArray(len)
        var i = 0

        while (!stack.empty()) {
            res[i++] = stack.pop()
        }

        return res
    }
}

3. 解法2 - 递归

3.1 Java

// 递归
class Solution {
    ArrayList<Integer> tmp = new ArrayList<Integer>();

    public int[] reversePrint(ListNode head) {
        recursion(head);
        int[] res = new int[tmp.size()];
        for (int i=0;i<res.length;i++) {
            res[i] = tmp.get(i);
        }
        return res;
    }

    // 递归的从尾到头添加结点值到tmp
    // 每访问一个节点的时候，先递归添加它后面的结点，再添加它本身
    public void recursion(ListNode head) {
        if(head == null)
            return;
        recursion(head.next);
        tmp.add(head.val);
    }
}

4. 参考

5. 笔记

上一页LEETCODE 32. 最长有效括号下一页LCOF 09. 用两个栈实现队列

最后更新于3年前