How to Print Immutable Linked List in Reverse using Recursion or
- 时间:2020-09-17 10:57:36
- 分类:网络文摘
- 阅读:99 次
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.Follow up:
Could you solve this problem in:
Constant space complexity?
Linear time complexity and less than linear space complexity?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].
Similar to How to Reverse a Linked List in Javascript?, we can have several ways to reverse a linked list. However, as the linked list here is iimmutable which means we can’t change the pointers of the nodes, we can although invoke the print function, thus we could use recursion or stack (First In Last Out) to achieve the task.
Recursive Reverse the Linked List
Recursion produces a short and clean code. If the current node is not NULL, we need to recursively call the print function and then print the current node (which is last).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | /** * // 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 { * 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(); } } };
Iteratively Reverse Printing a Linked List using a Stack
We could use a stack data structure (First In Last Out). Then we just need to follow the linked list and push each node to the stack. Then, we can remove a node from the stack one by one – which will be the reversed order of the linked list.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | /** * // 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) { stack<ImmutableListNode*> st; while (head) { st.push(head); head = head->getNext(); } while (!st.empty()) { auto p = st.top(); st.pop(); p->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) { stack<ImmutableListNode*> st; while (head) { st.push(head); head = head->getNext(); } while (!st.empty()) { auto p = st.top(); st.pop(); p->printValue(); } } };
Both implementations are O(N) space and O(N) time complexity.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:5 Tips for Bloggers to Stay Healthy Sanders Live-Tweets Republican Debate How to Check If Four Points can Make a Valid Square (C++ and Jav Python: Understanding the Importance of EigenValues and EigenVec How to Compute Kth Largest Element in a Stream? How to Flip Equivalent Binary Trees? How to Implement Quicksort Algorithm in Python – the Pytho How to Compute the Clumsy Factorials using Iterative Algorithm? How to Convert Float Number (Fraction) to Hexadecimal in Python? 4 Tips You Shouldn’t Miss While Creating Your Ideal Websit
- 评论列表
-
- 添加评论