几种从尾到头输出链表的算法比较

Reply Share

链表是一个是一种动态的线性结构，在创建链表时，无需知道链表的长度，每插入一个结点时，动态地为其分配内存，在输出链表时（单向链表），一般可沿着头指针逐步遍历所有节点，然而，要从尾到头遍历链表，可有以下几种思路：

几种从尾到头输出链表的算法比较

基本思路

在不破坏链表结构的前提下，对链表进行逆序输出，首先想到的应该是栈这样的一个结构，下面给出一个用栈实现的输出算法：

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
//链表数据结构
struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) :
             val(x), next(NULL) {
        }
  };

//利用栈结构对链表进行从尾到头输出
void printListFromTailToHead(ListNode* head){
    stack<ListNode> nodes;
    ListNode* pNode=head;
    while(pNode!=NULL){  //依次入栈
        nodes.push(pNode);
        pNode=pNode->next;
    }

    //出栈输出结构即可
    while(!nodes.empty()){
        pNode=nodes.top();
        cout<< pNode->val <<endl;
        nodes.pop();
    }
}

由于递归在本质上就是一个栈结构，既然可以利用栈实现该算法，则利用递归也可以实现，本算法的递归算法如下：

1
2
3
4
5
6
7
8
void printListFromTailToHead(ListNode* head){
    if(head !=NULL){
        if(head->next!=NULL){
           printListFromTailToHead(head->next);
        }
        cout<< head->val << endl;
    }
}

以上两种算法都可实现题目要求，但有时我们希望将输出作为一个函数返回值，方便以后对其进行调用，可对以上算法稍做修改即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> printListFromTailToHead(struct ListNode* head) {  
    stack<int> vestack;  
    vector<int> ret;    
  
    while (head != NULL){  
        vestack.push(head->val);  
        head = head->next;  
    }  
    while (!vestack.empty()){  
        int val = vestack.top();  
        ret.push_back(val);  
        vestack.pop();  
    }  
    return ret;  
}

递归算法实现

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> printListFromTailToHead(struct ListNode* head)  
{  
    vector<int> ret;  
  
    if (NULL != head){  
        if (NULL != head->next){  
            printListFromTailToHead(head->next);  
        }  
        ret.push_back(head->val);  
    }  
    return ret;  
}

现在可以有效从头到尾输出链表，并将结果存在一个vector结构中，但这里仍然存在一个严重的问题：
在利用递归实现该算法时，当链表的长度较长时，会出现栈溢出的问题，而递归本质上也是一种栈结构，所有上述四种方法可能都存在这样的隐患。 考虑到上述问题，既然利用vector对其进行存储，不妨在顺序遍历链表时依次将当前节点的val值插入到vector中。其实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> printListFromTailToHead(struct ListNode* head) {
        vector<int> result;
        ListNode* p=head;

        while(p){
        result.insert(result.begin(),p->val);  //依次插入当前节点的值
        p=p->next;
        }
        
        return result;        
     
    }

1