数据结构与算法之链表篇

一、关于链表常见问题

  1.比较顺序表和链表的优缺点

① 顺序表支持随机访问，单链表不支持随机访问
② 顺序表插入/删除数据效率很低，时间复杂度为O(N)（除尾插尾删），单链表插入/删除效率更高，时间复杂度为O(1)
③ 顺序表作为一种地址连续的存储结构其CPU高速缓存效率更高，单链表的存储地址是不连续的，其CPU高速缓存效率相比而言较低
那么在使用场景上需要注意在需要大量访问元素，而很少增删元素的可以使用顺序表，需要增删大量元素而不注重访问的考虑使用链表

  2.从尾到头打印单链表
链接：https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?tpId=13&&tqId=11156&rp=3&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
来源：牛客网

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/

 首先能想到的最简单的一个解法就是递归到最后一个节点，随着递归函数的结束返回从尾节点将所有节点的值压入数组中.但是这样当链过长时会栈溢出比较恶心

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> ArrayList;
        PrintListFromTailToHead(head,ArrayList);
        return  ArrayList;
    }
    
    void  PrintListFromTailToHead(ListNode* head,vector<int> &ArrayList)
    {
        if(head != NULL)
        {
            if(head->next != NULL)
            {
                PrintListFromTailToHead(head->next,ArrayList);
            }
            ArrayList.push_back(head->val);
        }
    }
};

 所以在联想一下排在前面的后打印，很像栈的数据特性，所以我们利用栈的先进后出的特性实现这个问题.

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        
        vector<int> ArrayList;
        stack<int> stacknode;
        ListNode* cur = head;
        //入栈
        while(cur != NULL)
        {
            stacknode.push(cur->val);
            cur = cur->next;
        }
        //出栈，将逆序后的链表元素放入 ArrayList
        while(!stacknode.empty())
        {
            ArrayList.push_back(stacknode.top());
            stacknode.pop();
        }
        return ArrayList;
    }
}; 

 除此之外还有一种比较简单的做法就是设立两个指针，一个指向当前节点，一个指向尾节点，初始化为nullptr，通过调整尾指针指向的节点来输出相应值，例如第一次先将尾结点调整到链表最后一个节点之后输出，然后将尾指针设立为当前节点，这样不断调整尾指针指向的节点直到其等于头结点时终止即可

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        
        ListNode* cur = nullptr;
        ListNode* tail = nullptr;
        vector<int> ArrayList;
        
        while(tail != head)
        {
            cur = head;
            while(cur->next != tail)
            {
                cur = cur->next;
            }
            tail = cur;
            ArrayList.push_back(tail->val);
        }
        return ArrayList;
    }
};