1265. 逆序打印不可变链表
给您一个不可变的链表，使用下列接口逆序打印每个节点的值：
ImmutableListNode: 描述不可变链表的接口，链表的头节点已给出。您需要使用以下函数来访问此链表（您 不能 直接访问 ImmutableListNode）：
ImmutableListNode.printValue()：打印当前节点的值。ImmutableListNode.getNext()：返回下一个节点。输入只用来内部初始化链表。您不可以通过修改链表解决问题。也就是说，您只能通过上述 API 来操作链表。
示例 1：
输入：head = [1,2,3,4] 输出：[4,3,2,1]
示例 2：
输入：head = [0,-4,-1,3,-5] 输出：[-5,3,-1,-4,0]
示例 3：
输入：head = [-2,0,6,4,4,-6] 输出：[-6,4,4,6,0,-2]
提示：
[1, 1000] 之间。[-1000, 1000] 之间。
进阶：
您是否可以：
原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2.3 MB, 提交时间: 2023-10-16 20:55:24
/* Below is the interface for ImmutableListNode, which is already defined for you.
*
* type ImmutableListNode struct {
*
* }
*
* func (this *ImmutableListNode) getNext() ImmutableListNode {
* // return the next node.
* }
*
* func (this *ImmutableListNode) printValue() {
* // print the value of this node.
* }
*/
func printLinkedListInReverse(head ImmutableListNode) {
current := head
for current != nil {
defer current.printValue()
current = current.getNext()
}
}
javascript 解法, 执行用时: 80 ms, 内存消耗: 44.9 MB, 提交时间: 2023-10-16 20:54:40
/**
* // This is the ImmutableListNode's API interface.
* // You should not implement it, or speculate about its implementation.
* function ImmutableListNode() {
* @ return {void}
* this.printValue = function() { // print the value of this node.
* ...
* };
*
* @return {ImmutableListNode}
* this.getNext = function() { // return the next node.
* ...
* };
* };
*/
/**
* @param {ImmutableListNode} head
* @return {void}
*/
var printLinkedListInReverse = function(head) {
if (head === null)
return;
let fastBegin = head.getNext();
while (fastBegin !== null) {
let slow = head;
let fast = fastBegin;
while (fast !== null) {
slow = slow.getNext();
fast = fast.getNext();
}
slow.printValue();
fastBegin = fastBegin.getNext();
}
head.printValue();
};
python3 解法, 执行用时: 128 ms, 内存消耗: 16.3 MB, 提交时间: 2023-10-16 20:54:26
# """
# This is the ImmutableListNode's API interface.
# You should not implement it, or speculate about its implementation.
# """
# class ImmutableListNode:
# def printValue(self) -> None: # print the value of this node.
# def getNext(self) -> 'ImmutableListNode': # return the next node.
class Solution:
def printLinkedListInReverse(self, head: 'ImmutableListNode') -> None:
if head is None:
return
fast_begin = head.getNext();
while fast_begin is not None:
slow = head
fast = fast_begin
while fast is not None:
slow = slow.getNext()
fast = fast.getNext()
slow.printValue()
fast_begin = fast_begin.getNext()
head.printValue()
java 解法, 执行用时: 4 ms, 内存消耗: 39.9 MB, 提交时间: 2023-10-16 20:54:09
/**
* // This is the ImmutableListNode's API interface.
* // You should not implement it, or speculate about its implementation.
* interface ImmutableListNode {
* public void printValue(); // print the value of this node.
* public ImmutableListNode getNext(); // return the next node.
* };
*/
class Solution {
public void printLinkedListInReverse(ImmutableListNode head) {
if (head == null)
return;
ImmutableListNode fastBegin = head.getNext();
while (fastBegin != null) {
ImmutableListNode slow = head;
ImmutableListNode fast = fastBegin;
while (fast != null) {
slow = slow.getNext();
fast = fast.getNext();
}
slow.printValue();
fastBegin = fastBegin.getNext();
}
head.printValue();
}
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 6.9 MB, 提交时间: 2023-10-16 20:53:50
/**
* // This is the ImmutableListNode's API interface.
* // You should not implement it, or speculate about its implementation.
* class ImmutableListNode {
* public:
* void printValue(); // print the value of the node.
* ImmutableListNode* getNext(); // return the next node.
* };
*/
class Solution {
public:
void printLinkedListInReverse(ImmutableListNode* head) {
if (head == nullptr)
return;
ImmutableListNode* fast_begin = head->getNext();
while (fast_begin != nullptr) {
ImmutableListNode* slow = head;
ImmutableListNode* fast = fast_begin;
while (fast != nullptr) {
slow = slow->getNext();
fast = fast->getNext();
}
slow->printValue();
fast_begin = fast_begin->getNext();
}
head->printValue();
}
};
java 解法, 执行用时: 0 ms, 内存消耗: 40.2 MB, 提交时间: 2023-10-16 20:53:31
/**
* // This is the ImmutableListNode's API interface.
* // You should not implement it, or speculate about its implementation.
* interface ImmutableListNode {
* public void printValue(); // print the value of this node.
* public ImmutableListNode getNext(); // return the next node.
* };
*/
class Solution {
public void printLinkedListInReverse(ImmutableListNode head) {
part(head, null);
}
// 这里区间是左闭右开
private void part(ImmutableListNode start, ImmutableListNode end) {
if (start.getNext() == end) {
// 由于左闭右开，此时区间中只剩一个节点了，打印并结束递归
start.printValue();
return;
}
// 使用快慢指针找到中间节点
ImmutableListNode mid;
for (ImmutableListNode p = start, q = start; ; p = p.getNext(), q = q.getNext().getNext()) {
if (q == end || q.getNext() == end) {
mid = p;
break;
}
}
// 因为要逆序，所以先递归后半部分
part(mid, end);
part(start, mid);
}
}