博客

描述

给您一个不可变的链表，使用下列接口逆序打印每个节点的值:

·

ImmutableListNode

:描述不可变链表的接口，链表的头节点已给出。

您需要使用以下函数来访问此链表(您不能直接访问

ImmutableListNode

):

·

ImmutableListNode.printValue()

:打印当前节点的值。

·

ImmutableListNode.getNext()

:返回下一个节点。

输入只用来内部初始化链表。您不可以通过修改链表解决问题。也就是说，您只能通过上述API来操作链表。

示例1：

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

示例2

输入：head = [-2,0,6,4,4,-6]
输出：[-6,4,4,6,0,-2]

提示:

·链表的长度在

[1,1000]

之间。

·每个节点的值在

[-1000,1000]

之间。

进阶:

· 使用常数级空间复杂度解决问题?

· 使用线性级时间复杂度和低于线性级时间复杂度解决问题?

话不多说，先说思路，一眼递归 ，直接递归到最后一个节点，然后开始输出，Java代码如下:

class Solution {
    public void printLinkedListInReverse(ImmutableListNode head) {
        if(head == null){
            return;
        }
        //找到最后一个结点
        printLinkedListInReverse(head.getNext());
        head.printValue();
    }
}

递归时间复杂度

显而易见，递归的时间复杂度是O(n)

其他解法

那么有没有其他方式的解法？我想到的是使用栈，本着偷懒原则，不想写了😂