面試C++?？嫉膯栴}：鏈表和數(shù)組有什么區(qū)別呢？

1、鏈表是鏈?zhǔn)酱鎯Y(jié)構(gòu)，數(shù)組是順序存儲結(jié)構(gòu)。
2、鏈表通過指針連接元素與元素，而數(shù)組則是把所有元素按順序進(jìn)行存儲。（就是說鏈表在內(nèi)存可以不連續(xù)，數(shù)組則是連續(xù)存儲的。）
3、鏈表的插入和刪除元素比較簡單，不需要移動元素，且較為容易實現(xiàn)長度的擴(kuò)充，但是查詢元素比較困難，數(shù)組是查詢比較快，但是刪除和增加會比較麻煩。（數(shù)組插入或刪除元素的時間復(fù)雜度O(n)，鏈表的時間復(fù)雜度O(1)。）
4、數(shù)組在使用前需要固定大小，如果太小，會導(dǎo)致數(shù)組越界；如果太大，會造成內(nèi)存資源浪費；而鏈表則能夠動態(tài)分配內(nèi)存，實現(xiàn)用多少申請多少
5、數(shù)組元素在棧區(qū)，鏈表元素在堆區(qū)；
6、數(shù)組使用完后系統(tǒng)自動釋放空間，鏈表使用完后需要人為通過free釋放空間；
7、數(shù)組利用下標(biāo)定位，時間復(fù)雜度為O(1)，鏈表定位元素時間復(fù)雜度O(n)（數(shù)組定位元素時可以根據(jù)下標(biāo)直接定位，而鏈表則需要遍歷，因此在定位元素時，數(shù)組優(yōu)于鏈表）

所以。。。。什么是鏈表呢？直接上栗子??！

單向鏈表

單向鏈表中包含數(shù)據(jù)域和指針域，其中數(shù)據(jù)域用于存放數(shù)據(jù)，指針域用來連接當(dāng)前結(jié)點和下一節(jié)點。

struct Node {
  int value;
  Node *next;
};

雙向鏈表

雙向鏈表中同樣有數(shù)據(jù)域和指針域，不同之處在于指針域有左右（或上一個、下一個）之分，用來連接上一個節(jié)點、當(dāng)前結(jié)點、下一個結(jié)點。

struct Node {
  int value;
  Node *left;
  Node *right;
};

一個簡單的應(yīng)用就是反轉(zhuǎn)鏈表:

輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL

假設(shè)鏈表為 1→2→3→?，我們想要把它改?←1←2←3。

在遍歷鏈表時，將當(dāng)前節(jié)點的 next 指針改為指向前一個節(jié)點。由于節(jié)點沒有引用其前一個節(jié)點，因此必須事先存儲其前一個節(jié)點。在更改引用之前，還需要存儲后一個節(jié)點。最后返回新的頭引用。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

[參考鏈接]
https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/solution/fan-zhuan-lian-biao-by-leetcode-solution-jvs5/
https://www.html.cn/qa/other/21664.html
https://blog.csdn.net/weixin_30636089/article/details/97230131
https://oi-wiki.org/ds/monotonous-stack/