Welcome to Subscribe On Youtube

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

Similar to 206 Reverse Linked List

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.

Follow up, could you solve this problem in:

Constant space complexity?

This solution uses a recursive approach to traverse the linked list in reverse order without using any additional space. The printLinkedListInReverse method calls a helper function reversePrint recursively. It first recursively traverses to the end of the list and then prints the values in reverse order while backtracking.

Question for above recursion solution: it’s a recursion, but recursion is also using memory’s stack to store the previous recursions, why it’s Constant Space Complexity?

  • Recursion typically uses the call stack to store previous function calls. However, in the case of the Constant Space Complexity solution for leetcode 1265, the key factor is that the space used by the recursion does not scale with the input size.
  • Although the recursion does use the call stack to store intermediate function calls, the maximum depth of the recursion is limited by the number of nodes in the linked list. In other words, the depth of the recursion is determined by the size of the input, rather than growing indefinitely with the input size.
  • Since the maximum depth of the recursion is bounded by a constant (the number of nodes in the linked list), the space complexity is considered constant. Regardless of the input size, the amount of additional space used by the recursion remains the same, making it a constant factor.
  • Therefore, in this algorithmn, “constant” refers to the fact that the amount of additional space used by the recursion does not grow with the input size, rather than implying that no memory is used at all.
Linear time complexity and less than linear space complexity?

In this solution, we first calculate the count of nodes in the linked list using the getNodeCount method, which iterates through the list and counts the nodes.

Then, the printListReverse method recursively prints the list in reverse order. It keeps track of the remaining count of nodes and only proceeds to print if there are more than one node left. The method calls itself recursively with the next node and decreases the count by one in each recursive call until reaching the base case (either a None node or a count of zero). Then it prints the value of the current node.

Both of these solutions satisfy the specified requirements, achieving constant space complexity or linear time complexity with less than linear space complexity.

  • /**
 * // 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();
        }
    }
};

  • # """
# 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:
        stack = []

        while head:
            stack.append(head)
            head = head.getNext()

        while stack:
            stack.pop().printValue()

##############

class Solution: # follow up: Constant Space Complexity
    def printLinkedListInReverse(self, head: 'ImmutableListNode') -> None:
        if head:
            self.printLinkedListInReverse(head.getNext())
            head.printValue()


##############

class Solution_followup: # follow up: Linear Time Complexity and Less Than Linear Space Complexity
    def printLinkedListInReverse(self, head: 'ImmutableListNode') -> None:
        if not head:
            return

        # Count nodes
        n = self.get_count(head)

        # Print one by one
        for i in range(n, 0, -1):
            self.print_nth(head, i)

    def get_count(self, head: 'ImmutableListNode') -> int:
        count = 0
        current = head
        while current:
            count += 1
            current = current.getNext()
        return count

    def print_nth(self, head: 'ImmutableListNode', n: int) -> None:
        curr = head
        for i in range(n - 1):
            if not curr:
                return
            curr = curr.getNext()

        curr.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();
        }
    }
}

All Problems

All Solutions