剑指 Offer 06. 从尾到头打印链表

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

示例 1:

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

限制:

0 <= 链表长度 <= 10000

解决方案

后进先出,可使用栈。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        ListNode node = head;
        while (node != null) {
            stack.push(node.val);
            node = node.next;
        }
        int[] result = new int[stack.size()];
        int i = 0;
        while (!stack.empty()) {
            result[i++] = stack.pop();
        }
        return result;
    }
}

书中还提到了递归实现,不过,不同点在于,书中直接打印到标准输出流上,而LeetCode上本题需要返回一个int[]。直接反向写入这个要返回的数组更快,也节省内存。

class Solution {
    public int[] reversePrint(ListNode head) {
        int size = 0;
        ListNode node = head;
        while (node != null) {
            size += 1;
            node = node.next;
        }

        node = head;
        int[] result = new int[size];
        for (int i = size - 1; i >= 0 && node != null; --i) {
            result[i] = node.val;
            node = node.next;
        }
        return result;
    }
}
/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun reversePrint(head: ListNode?): IntArray {
        var size = 0
        var node = head
        while (node != null) {
            size += 1
            node = node.next
        }

        node = head
        val result = IntArray(size)
        for (i in result.lastIndex downTo 0) {
            result[i] = node?.`val` ?: throw Exception()
            node = node.next
        }
        return result
    }
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据