Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/1265.html
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?
Algorithm
Similar to 206 Reverse Linked List
DFS, recursion before print current node.
- space is O(N), since need to store previous recursion
Follow up
Could you solve this problem in:
Constant space complexity? Linear time complexity and less than linear space complexity?
Code
-
public class Print_Immutable_Linked_List_in_Reverse { /* Algorithms: 1) Find n = count nodes in linked list. 2) For i = n to 1, do following. Print i-th node using get n-th node function */ public class Solution_followup { public void printLinkedListInReverse(ImmutableListNode head) { if (head == null) { return; } // Count nodes int n = getCount(head); // print one by one for (int i = n; i >= 1; i--) { printNth(head, i); } } /* Counts no. of nodes in linked list */ private int getCount(ImmutableListNode head) { int count = 0; // Initialize count ImmutableListNode current = head; // Initialize current while (current != null) { count++; current = current.getNext(); } return count; } /* Takes head pointer of the linked list and index as arguments and return data at index*/ private void printNth(ImmutableListNode head, int n) { ImmutableListNode curr = head; for (int i = 0; i < n - 1 && curr != null; i++) { curr = curr.getNext(); } curr.printValue(); } } public class Solution { public void printLinkedListInReverse(ImmutableListNode head) { if (head == null) { return; } // recursion before print current node printLinkedListInReverse(head.getNext()); head.printValue(); } } interface ImmutableListNode { void printValue(); // print the value of this node. ImmutableListNode getNext(); // return the next node. } } ############ /** * // 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(); } } }
-
// OJ: https://leetcode.com/problems/print-immutable-linked-list-in-reverse/ // Time: O(N) // Space: O(N) class Solution { public: void printLinkedListInReverse(ImmutableListNode* head) { if (!head) return; printLinkedListInReverse(head->getNext()); head->printValue(); } }; class Solution { public: void printLinkedListInReverse(ImmutableListNode* head) { stack<ImmutableListNode*> stack; while (head) { stack.push(head); head = head->getNext(); } while (!stack.empty()) stack.top()->printValue(), stack.pop(); } }; /** * // 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(); // Returns the next node. * }; */
-
# """ # 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() class Solution: def printLinkedListInReverse(self, head: 'ImmutableListNode') -> None: stack = [] while head: stack.append(head) head = head.getNext() while stack: stack.pop().printValue() class Solution_followup: 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(); } }