Question

1265. Print Immutable Linked List in Reverse

中文文档

Description

You are given an immutable linked list, print out all values of each node in reverse with the help of the following interface:

• ImmutableListNode: An interface of immutable linked list, you are given the head of the list.

You need to use the following functions to access the linked list (you can't access the ImmutableListNode directly):

• ImmutableListNode.printValue(): Print value of the current node.
• ImmutableListNode.getNext(): Return the next node.

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.

 

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].

 

Follow up:

Could you solve this problem in:

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

Solutions

Solution 1: Recursion

We can use recursion to implement reverse printing of a linked list. In the function, we check whether the current node is null. If it is not null, we get the next node, then recursively call the function itself, and finally print the value of the current node.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the length of the linked list.

# """
# 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:
      self.printLinkedListInReverse(head.getNext())
      head.printValue()

/**
 * // 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) {
      printLinkedListInReverse(head.getNext());
      head.printValue();
    }
  }
}

/**
 * // 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) {
      printLinkedListInReverse(head->getNext());
      head->printValue();
    }
  }
};

/*   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) {
  if head != nil {
    printLinkedListInReverse(head.getNext())
    head.printValue()
  }
}

/**
 * // This is the ImmutableListNode's API interface.
 * // You should not implement it, or speculate about its implementation
 * class ImmutableListNode {
 *    printValue() {}
 *
 *    getNext(): ImmutableListNode {}
 * }
 */

function printLinkedListInReverse(head: ImmutableListNode) {
  if (head) {
    printLinkedListInReverse(head.next);
    head.printValue();
  }
}

/**
 * // 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 this node.
 *   public ImmutableListNode GetNext(); // return the next node.
 * }
 */

public class Solution {
  public void PrintLinkedListInReverse(ImmutableListNode head) {
    if (head != null) {
      PrintLinkedListInReverse(head.GetNext());
      head.PrintValue();
    }
  }
}