1265

1265. Print Immutable Linked List in Reverse (Medium)

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?

Companies:
Facebook

Related Topics:
Linked List, Two Pointers, Stack, Recursion

Solution 1. Recursion

// OJ: https://leetcode.com/problems/print-immutable-linked-list-in-reverse/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    void printLinkedListInReverse(ImmutableListNode* head) {
        if (!head) return;
        printLinkedListInReverse(head->getNext());
        head->printValue();
    }
};

Solution 2. Brute force

// OJ: https://leetcode.com/problems/print-immutable-linked-list-in-reverse/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
    void printLinkedListInReverse(ImmutableListNode* head) {
        ImmutableListNode* last = NULL;
        while (last != head) {
            auto p = head;
            while (p->getNext() != last) p = p->getNext(); 
            p->printValue();
            last = p;
        }
    }
};

Solution 3. Sqrt Decomposition

We break the list into batches, each of which is of length sqrt(N). We store all heads of batches in a stack. After the stack is filled, we start popping the stack, and for each popped head, we use the recursive print method in Solution 1 to print this batch.

Complexity Analysis

getLength takes O(N) time and O(1) space.

Filling the stack takes O(N) time and O(sqrt(N)) space.

Printing each batch takes O(sqrt(N)) time and O(sqrt(N)) space. Because there are sqrt(N) batches, this popping stack and printing step takes O(sqrt(N) * sqrt(N)) = O(N) time and O(sqrt(N)) space (the space doesn't add up).

// OJ: https://leetcode.com/problems/print-immutable-linked-list-in-reverse/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(sqrt(N))
class Solution {
    int getLength(ImmutableListNode *head) {
        int ans = 0;
        for (; head; head = head->getNext(), ++ans);
        return ans;
    }
    void print(ImmutableListNode *head, int len) {
        if (!head || !len) return;
        print(head->getNext(), len - 1);
        head->printValue();
    }
public:
    void printLinkedListInReverse(ImmutableListNode* head) {
        int len = ceil(sqrt(getLength(head)));
        stack<ImmutableListNode*> s;
        for (int i = 0; head; head = head->getNext(), ++i) {
            if (i % len == 0) s.push(head);
        }
        while (s.size()) {
            print(s.top(), len);
            s.pop();
        }
    }
};