一茬祷、基本概念
鏈表是一種物理存儲(chǔ)單元上非連續(xù)清焕、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?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)典問(wèn)題：約瑟夫問(wèn)題激挪。
例題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)處理過(guò)程。
1瞻赶、重點(diǎn)考慮相鄰結(jié)點(diǎn)的指針改變赛糟，推薦畫(huà)圖法。
2砸逊、在指定指針的情況下插入結(jié)點(diǎn)璧南，時(shí)間復(fù)雜度O（1），分為頭插法和尾插兩種师逸。
3司倚、如果沒(méi)有指定指針的時(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)，推薦畫(huà)圖法淆攻。
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弄贿，也就是說(shuō)每一個(gè)數(shù)組的下標(biāo)都要對(duì)應(yīng)一個(gè)data和一個(gè)cur春锋。
數(shù)據(jù)域data用來(lái)存放數(shù)據(jù)元素，也就是通常我們要處理的數(shù)據(jù)差凹，而cur相當(dāng)于單鏈表中的next指針期奔，存放該元素的后繼在數(shù)組中的下標(biāo)，我們把cur叫做游標(biāo)危尿。
5.2呐萌、示例圖：
六、常見(jiàn)面試題：
例題1：給定一個(gè)排序鏈表谊娇，刪除所有重復(fù)的元素肺孤，使得每個(gè)元素只出現(xiàn)一次。
示例 1:
輸入: 1->1->2
輸出: 1->2
示例 2:
輸入: 1->1->2->3->3
輸出: 1->2->3
思路：
鏈表中刪除元素济欢，即操作指針指向下一個(gè)元素赠堵，跳過(guò)當(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)，從尾到頭反過(guò)來(lái)返回每個(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è)新的 升序 鏈表并返回吗垮。新鏈表是通過(guò)拼接給定的兩個(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
撰寫(xiě)記錄
2020.12.26-08:00:00-第一次撰寫(xiě)
2021.01.05-07:30:00-第二次撰寫(xiě)
2021.01.09-11:08:10-第三次撰寫(xiě)
2021.02.09-21:56:00-第四次撰寫(xiě)
