関小君刷题记

题目大意：

反向打印链表

给定一个固定链表，利用以下接口倒序打印出链表中的每个节点的值

• ImmutableListNode: 一个链表的接口，题目将给你一个链表头元素的对象

你只能通过以下方式来访问链表

• ImmutableListNode.printValue(): 打印当前节点的数值
• ImmutableListNode.getNext(): 返回链表下一个节点

The input is only given to initialize the linked list internally. You must solve this problem without modifying the linked list. In other words, you must operate the linked list using only the mentioned APIs.

Follow up:

Could you solve this problem in:

• Constant space complexity?
• Linear time complexity and less than linear space complexity?

Example 1:

Input: head = [1,2,3,4]
Output: [4,3,2,1]

Example 2:

Input: head = [0,-4,-1,3,-5]
Output: [-5,3,-1,-4,0]

Example 3:

Input: head = [-2,0,6,4,4,-6]
Output: [-6,4,4,6,0,-2]

Constraints:

• The length of the linked list is between [1, 1000].
• The value of each node in the linked list is between [-1000, 1000].

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1265

解题思路分析：

这道题目非常简单，想要倒序打印链表只需要一个递归就可以解决。简单来说，就是先一路递归到链表末尾，打印当前节点的值，退回到上一层递归，再打印当前节点的值，一直退回到最上层递归之后，即倒序打印了一遍链表。

实现代码：

public void printLinkedListInReverse(ImmutableListNode head) {
    // 如果当前节点为空，退出
    if(head==null) return;
    // 先一路递归到最后一个节点
    printLinkedListInReverse(head.getNext());
    // 打印当前节点
    head.printValue();
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 100.00% of Java online submissions for Print Immutable Linked List in Reverse.

Memory Usage: 36.2 MB, less than 100.00% of Java online submissions for Print Immutable Linked List in Reverse.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1265-print-immutable-linked-list-in-reverse-解题思路分析/