一、基本概念
鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的；
鏈表存在多種形式。包括循環(huán)鏈表，單鏈表，雙向鏈表，靜態(tài)鏈表。
二、循環(huán)鏈表
2.1、基本實(shí)現(xiàn)和特性：
1、尾結(jié)點(diǎn)指針指向頭結(jié)點(diǎn)的鏈表
2、可以是單鏈表，也可以是雙鏈表
2.2、總結(jié)
1、優(yōu)點(diǎn)是從鏈尾到鏈頭十分方便。
2、經(jīng)典問題：約瑟夫問題。
例題1：83. 刪除排序鏈表中的重復(fù)元素https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
三、單鏈表
3.1、基本實(shí)現(xiàn)和特性
每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域，只有一個(gè)后繼結(jié)點(diǎn)。
3.2、重點(diǎn)概念
頭結(jié)點(diǎn)， 尾結(jié)點(diǎn)
3.3、操作
3.3.1、建立鏈表：本質(zhì)上就是不斷的插入結(jié)點(diǎn)。
3.3.2、插入結(jié)點(diǎn)：就是申請(qǐng)空間，得到數(shù)據(jù)，建立鏈接的循環(huán)處理過程。
1、重點(diǎn)考慮相鄰結(jié)點(diǎn)的指針改變，推薦畫圖法。
2、在指定指針的情況下插入結(jié)點(diǎn)，時(shí)間復(fù)雜度O（1），分為頭插法和尾插兩種。
3、如果沒有指定指針的時(shí)候，則需要遍歷先確定插入位置，再執(zhí)行2，時(shí)間復(fù)雜度O（n）
4、注意頭結(jié)點(diǎn)的插入
3.3.3、刪除結(jié)點(diǎn)：
1、刪除結(jié)點(diǎn)中“值為給定某個(gè)值”的結(jié)點(diǎn)，時(shí)間復(fù)雜度O（1）。
2、刪除給定指針的結(jié)點(diǎn)，需要遍歷前驅(qū)結(jié)點(diǎn)，時(shí)間復(fù)雜度O（n）。
3、注意刪除頭結(jié)點(diǎn)，尾結(jié)點(diǎn)，推薦畫圖法。
3.3.4、和數(shù)組性能比較：
3.3.5、查找結(jié)點(diǎn)：
1、根據(jù)指針依次查找，直到找到相應(yīng)的結(jié)點(diǎn)（考慮多個(gè)的情況）
2、時(shí)間復(fù)雜度O（n）
四、雙向鏈表
4.1、基本概念和特性：
單向鏈表只有一個(gè)方向，結(jié)點(diǎn)只有一個(gè)后繼指針next指向后面的結(jié)點(diǎn)，雙向鏈表支持兩個(gè)方向，每個(gè)結(jié)點(diǎn)不止有一個(gè)后繼指針next指向后面的結(jié)點(diǎn)，還有一個(gè)前驅(qū)指針prev指向前面的結(jié)點(diǎn)，占用更多空間的同時(shí)，插入和刪除效率更高。
4.2、操作：
1、刪除給定指針指向的結(jié)點(diǎn)，直接獲取前驅(qū)結(jié)點(diǎn)，不需要遍歷，時(shí)間復(fù)雜度為O（1），插入的情況類似刪除
2、實(shí)際使用例子：java的LinkedHashMap
3、空間換時(shí)間的思想
五、靜態(tài)鏈表
5.1、基本概念和特征：
用數(shù)組描述的鏈表，稱為靜態(tài)鏈表。
首先讓數(shù)組的元素都是由兩個(gè)數(shù)據(jù)域構(gòu)成，data和cur，也就是說每一個(gè)數(shù)組的下標(biāo)都要對(duì)應(yīng)一個(gè)data和一個(gè)cur。
數(shù)據(jù)域data用來存放數(shù)據(jù)元素，也就是通常我們要處理的數(shù)據(jù)，而cur相當(dāng)于單鏈表中的next指針，存放該元素的后繼在數(shù)組中的下標(biāo)，我們把cur叫做游標(biāo)。
5.2、示例圖：
六、常見面試題：
例題1：給定一個(gè)排序鏈表，刪除所有重復(fù)的元素，使得每個(gè)元素只出現(xiàn)一次。
示例 1:
輸入: 1->1->2
輸出: 1->2
示例 2:
輸入: 1->1->2->3->3
輸出: 1->2->3
思路：
鏈表中刪除元素，即操作指針指向下一個(gè)元素，跳過當(dāng)前元素，即完成刪除操作。
時(shí)間復(fù)雜度：O（n），n為節(jié)點(diǎn)的個(gè)數(shù)
空間復(fù)雜度：O（1）
代碼實(shí)現(xiàn)：
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
cur = head
while cur and cur.next:
if cur.val == cur.next.val:
cur.next = cur.next.next
else:
cur = cur.next
return head
例題2：從尾到頭打印鏈表 https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
輸入一個(gè)鏈表的頭節(jié)點(diǎn)，從尾到頭反過來返回每個(gè)節(jié)點(diǎn)的值（用數(shù)組返回）。
示例 1：
輸入：head = [1,3,2]
輸出：[2,3,1]
思路：
思路：循環(huán)head節(jié)點(diǎn)，指針移動(dòng)到下一位，直到head為空
時(shí)間復(fù)雜度：O（n），n為節(jié)點(diǎn)的個(gè)數(shù)
空間復(fù)雜度：O（1）
代碼實(shí)現(xiàn)：
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
res = []
while head:
res.append(head.val)
head = head.next
return res[::-1]
例題3：21. 合并兩個(gè)有序鏈表 https://leetcode-cn.com/problems/merge-two-sorted-lists/
將兩個(gè)升序鏈表合并為一個(gè)新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。
示例 1：
輸入：l1 = [1,2,4], l2 = [1,3,4]
輸出：[1,1,2,3,4,4]
示例 2：
輸入：l1 = [], l2 = []
輸出：[]
示例 3：
輸入：l1 = [], l2 = [0]
輸出：[0]
思路：
遞歸，判斷l(xiāng)1和l2的值的大小，如果l1的val小，則l1指向l1和l2的合并后的結(jié)果，反之，則l2指向l1和l2的合并后的結(jié)果
時(shí)間復(fù)雜度：O（n），n為l1和l2的節(jié)點(diǎn)的個(gè)數(shù)
空間復(fù)雜度：O（1）
代碼實(shí)現(xiàn)：
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1:
return l2
if not l2:
return l1
if l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l2.next, l1)
return l2
例題4： 24. 兩兩交換鏈表中的節(jié)點(diǎn)https://leetcode-cn.com/problems/swap-nodes-in-pairs/
給定一個(gè)鏈表，兩兩交換其中相鄰的節(jié)點(diǎn)，并返回交換后的鏈表。
你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換。
示例 1：
輸入：head = [1,2,3,4]
輸出：[2,1,4,3]
示例 2：
輸入：head = []
輸出：[]
示例 3：
輸入：head = [1]
輸出：[1]
思路：
增加前指針指向本身，交換a，b元素，依次循環(huán)下去，返回前指針
T：O（n），n為節(jié)點(diǎn)的個(gè)數(shù)， S：O（1）
時(shí)間復(fù)雜度：O（n），n為節(jié)點(diǎn)的個(gè)數(shù)
空間復(fù)雜度：O（1）
代碼實(shí)現(xiàn)：
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
pre, pre.next = self, head
while pre.next and pre.next.next:
a = pre.next
b = a.next
pre.next, a.next, b.next = b, b.next, a
pre = a
return self.next
撰寫記錄
2020.12.26-08:00:00-第一次撰寫
2021.01.05-07:30:00-第二次撰寫
2021.01.09-11:08:10-第三次撰寫
2021.02.09-21:56:00-第四次撰寫
