政子的博客

技术|学习|随笔

CodingInterview-从尾到头打印链表

使用递归可以很轻松解决这个问题，不过如果链表太长，可能会造成函数调用栈溢出的情况。

只遍历了一遍链表，所以时间复杂度是 O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int>* vect=new vector<int>();
        this->printElements(vect,head);
        return *vect;
    }
    void printElements(vector<int>* vect,ListNode* node){
        if(node!=NULL){
            this->printElements(vect,node->next);
            vect->push_back(node->val);
        }
    }
};

第二种思路是可以先遍历一遍链表，找到链表得长度，然后申请该长度的 vector，最后再次遍历链表，逆序填入 vector 中。由于只遍历了两遍 vector，其时间复杂度依旧是 O(n)。

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
26
27
/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        int n=0;
        ListNode* p=head;
        while(p!=NULL){
            p=p->next;
            n++;
        }
        vector<int> vect(n);
        p=head;
        while(--n>=0){
            vect[n]=p->val;
            p=p->next;
        }
        return vect;
    }
};

还能想到的一些其它解法

  • 用栈倒一遍：和第二种思路差不多，但是要多花一些空间
  • 把链表先逆序，然后直接输出：这种改变了输入，感觉不怎么好
  • 使用 vector 的 inser 方法[vect.insert(vect.begin(),head->val)]：我对 C++不是很熟，不清楚 vector 的 insert 方法复杂度如何