## 鏈表 由于數組在插入和刪除操作，都需要后面的結點。內存需要預先分配，擴容不易。 所以有了鏈表。鏈表包含一個指向下一個節點的指針和一個自己data域 > 鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列節點組成，這些節點不必在內存中相連。每個節點由數據部分Data和鏈部分Next，Next指向下一個節點，這樣當添加或者刪除時，只需要改變相關節點的Next的指向，效率很高。 ```c_cpp struct Node { void * data; Node *next; } Node ``` 頭指針：指向鏈表鏈表第一個元素的指針 頭結點：就是一個含有空的數據域的結點。作為標識。 鏈表的結構  單鏈表的操作 - 查找 查找元素的時間復雜度依然是O（n）。需要從頭節點遍歷。 - 插入 插入一個新的元素到指定的位置，只需要改變前面元素的next指針指向該元素。不需要移動后面的元素。時間復雜度為0（n） - 刪除 刪除一個元素的，只需要記住這個元素的前一個元素和后面一個元素。刪掉這個元素后，采用覆蓋的方法，實現刪除。時間復雜度為O（1） ### 雙鏈表 雙鏈表是包含兩個兩個指針域和一個data域的鏈表結構。這樣我們可以從兩個方向遍歷。 ```c_cpp struct doubleLink { void *data; struct doubleLink next; struct doubleLink prev; } ``` ### 鏈表相關的面試題 鏈表是一種基礎的數據結構，也是面試中常考的， - 判斷單鏈表是否有環 可以使用快慢指針來。如果有環，則兩個指針會相遇。 - 已知兩個單鏈表相交，求他們的第一個交點 思路：由于兩個單鏈表相交，那么他們的尾節點一定是相同的。遍歷兩個鏈表，求出各個長度。然后求出兩個鏈表的差N，然后讓長的鏈表，先走N,慢的鏈表再同步走。當兩個節點相同時。就是一個第一個交點 - 快速找到未知長度單鏈表的中間節點 思路1：最簡單的方法，遍歷一次單鏈表，然后求出長度。然后除以2。找到位置，然后再遍歷一次。時間復雜度是O（(3N/2)） 思路2：快慢指針，快的指針比慢指針多走一倍，然后快的指針走到尾，慢指針恰好在中間。 - 約瑟夫環 > 在羅馬人占領喬塔帕特后，39個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧愿死也不要被敵人抓到，于是決定了一個自殺方式，41個人排成一個圓圈，由第1個人開始報數，每報數到第3人該人就必須自殺，然后再由下一個重新報數，直到所有人都自殺身亡為止。然而Josephus和他的朋友并不想遵從，Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲。 思路：可以使用循環鏈表的方法。