谷歌09/06电面挂经

根据题意描述给了解答．有问题的话欢迎指正，或者给个赞．

1. #include <iostream>
   
2. 
   
3. class LinkedNode
   
4. {
   
5.     public:
   
6.     int val;
   
7.     LinkedNode* next;
   
8.     LinkedNode(int a)
   
9.     {
   
10.         next = NULL;
    
11.         val = a;
    
12.     }
    
13. };
    
14. 
    
15. void solution(LinkedNode* head, int N)
    
16. {
    
17.     vector<LinkedNode*>array;   
    
18.     LinkedNode* h = head;
    
19.    
    
20.     array.push_back(h);
    
21.     for (int i=0; i<N; i++)
    
22.     {        
    
23.         if (i%int(sqrt(N)+1)==0)        
    
24.             array.push_back(h);
    
25.         h = h->next;        
    
26.     }
    
27.     array.push_back(NULL);
    
28.    
    
29.     for (int i=array.size()-2; i>=0; i--)
    
30.     {
    
31.         LinkedNode* p =array[i];
    
32.         vector<int>temp;
    
33.         while (p!=array[i+1])
    
34.         {
    
35.             temp.push_back(p->val);
    
36.             p = p->next;
    
37.         }            
    
38.         for (int j=temp.size()-1; j>=0; j--)
    
39.             cout<<temp[j]<<" ";
    
40.     }   
    
41. }
    
42. 
    
43. int main()
    
44. {
    
45.     LinkedNode* head = new LinkedNode(1);
    
46.     LinkedNode* h = head;
    
47.     h->next = new LinkedNode(2);
    
48.     h = h->next;
    
49.     h->next = new LinkedNode(3);
    
50.     h = h->next;
    
51.     h->next = new LinkedNode(4);
    
52.     h = h->next;
    
53.     h->next = new LinkedNode(5);
    
54.     h = h->next;
    
55.     h->next = new LinkedNode(6);
    
56.     h = h->next;
    
57.     h->next = new LinkedNode(7);
    
58.     h = h->next;
    
59.     h->next = new LinkedNode(8);
    
60.     h = h->next;
    
61.    
    
62.     solution(head,8);
    
63. 
    
64. }

复制代码

这种题真的不给活路。。。

wisdompeak2 发表于 2018-9-22 03:53
根据题意描述给了解答．有问题的话欢迎指正，或者给个赞．
[mw_shl_code=cpp,true]#include

请问这个时间复杂度 和空间复杂度是多少？

请问 大佬 这个解法 对吗 https://stackoverflow.com/questions/41542257/reverse-print-an-immutable-linked-list-with-less-than-on-space

dengzeyu147 发表于 2018-10-9 11:11
请问这个时间复杂度 和空间复杂度是多少？

时间是o(n)，空间是o(sqrt(n))