問題描述：【Linked List、Recursion】24. Swap Nodes in Pairs
解題思路：
這道題是給一個(gè)鏈表，相鄰結(jié)點(diǎn)數(shù)值兩兩進(jìn)行交換，要求不修改結(jié)點(diǎn)值且只能操作鏈表本身。
方法1：三指針完成交換
鏈表中一般涉及兩個(gè)結(jié)點(diǎn)交換的操作，基本上需要相鄰的三個(gè)指針 pre1，pre2，cur 完成三次交換操作，然后再移動三個(gè)指針到下一個(gè)正確的位置。
因此，我們只需要循環(huán) cur 的位置，往后一直遍歷直到鏈表為空為止。
在這道題中，因?yàn)槭莾蓛山粨Q，所以方便的解法就是建立一個(gè)空給點(diǎn) node，作為鏈表的頭結(jié)點(diǎn) head，最后返回的 head.next 就是答案。
注意在交換的過程中，每次交換的三個(gè)操作要保證鏈表不能斷。
時(shí)間復(fù)雜度 O(n)，空間復(fù)雜度 O(1)。
Python3 實(shí)現(xiàn)：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
if head == None or head.next == None: return head
node = ListNode(-1) # 頭部插入一個(gè)空結(jié)點(diǎn)
node.next = head
head = node
# 三指針法
pre2, pre1, cur = head, head.next, head.next.next
while cur:
pre2.next = cur # 交換
pre1.next = cur.next
cur.next = pre1
pre2 = pre1 # 修改
pre1 = pre1.next
if pre1 == None: break # 防止pre1.next為空
cur = pre1.next
return head.next
方法2：遞歸
這道題實(shí)際上還可以使用遞歸（只不過不太好想，看了別人的代碼才恍然大悟）。
1、函數(shù)的返回值：交換后的鏈表的頭結(jié)點(diǎn) head。
2、遞歸函數(shù)做了什么：假設(shè) 1->2->3->4->5->...，遞歸函數(shù)完成了 3->4->5... 的交換 swapPairs(head.next.next)，并返回了指向 4 的 head，因此需要建一個(gè) second 指向 2，然后將 head.next 指向遞歸函數(shù)的返回值，并將 second 作為頭結(jié)點(diǎn) head，最后返回 second。
3、遞歸出口：如果鏈表為空或者 head.next 為空，就之間返回 head。
總之，你不用去想遞歸函數(shù) swapPairs() 后面的交換是怎么完成的，只需要知道它能夠完成交換即可（或許這就是遞歸的精髓吧）。
時(shí)間復(fù)雜度 O(n)，空間復(fù)雜度 O(1)。
Python3 實(shí)現(xiàn)：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
if head == None or head.next == None: # 遞歸出口
return head
second = head.next
head.next = self.swapPairs(head.next.next)
second.next = head
return second
問題描述：【Linked List、Tree】109. Convert Sorted List to Binary Search Tree
解題思路：
這道題是給一個(gè)有序鏈表，將其轉(zhuǎn)化為高度平衡的二叉搜索樹。
要將有序鏈表轉(zhuǎn)化為高度平衡的二叉搜索樹，就需要從鏈表的中間斷開，然后對于左右鏈表就行遞歸調(diào)用即可。具體細(xì)節(jié)：
1、鏈表查找中間點(diǎn)可以通過快慢指針來操作。
2、找到中點(diǎn)后，要以中點(diǎn)的值建立一個(gè)樹的根結(jié)點(diǎn)，再把原鏈表斷開，分為前后兩個(gè)鏈表，都不能包含原中結(jié)點(diǎn)，然后再分別對這兩個(gè)鏈表遞歸調(diào)用原函數(shù)，分別連上左右子結(jié)點(diǎn)即可。
時(shí)間復(fù)雜度為 O(nlogn)，空間復(fù)雜度為 O(1)。
Python3 實(shí)現(xiàn)：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def sortedListToBST(self, head: ListNode) -> TreeNode:
if head == None:
return None
if head.next == None:
return TreeNode(head.val)
pre = None # 記錄 slow 的前一個(gè)結(jié)點(diǎn)，便于斷開左右鏈表
slow = fast = head
while fast and fast.next:
pre = slow
slow = slow.next
fast = fast.next.next
pre.next = None # 從中間斷開
node = TreeNode(slow.val)
node.left = self.sortedListToBST(head) # [head, slow-1] 左區(qū)間
node.right = self.sortedListToBST(slow.next) # [slow+1,] 右區(qū)間
return node
問題描述：【Linked List】328. Odd Even Linked List
解題思路：
這道題是給一個(gè)鏈表，將奇數(shù)位置的數(shù)按位置順序排在鏈表前面，偶數(shù)位置的數(shù)按位置順序排在鏈表后面。要求空間復(fù)雜度 O(1)，時(shí)間復(fù)雜度 O(n)。
設(shè)置三個(gè)指針，一個(gè)指向奇數(shù)尾部的指針 p，一個(gè)指向當(dāng)前結(jié)點(diǎn) cur，一個(gè)指向當(dāng)前結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn) pre。遍歷 cur 的過程中交換三個(gè)指針的指向，然后再移動它們到下一個(gè)正確的位置即可。
Python3 實(shí)現(xiàn)：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def oddEvenList(self, head: ListNode) -> ListNode:
if head == None: return None
p = pre = head # p: 奇數(shù)尾結(jié)點(diǎn), pre: cur的前一個(gè)結(jié)點(diǎn)
cur = head.next # 當(dāng)前結(jié)點(diǎn)
while cur:
pre = pre.next
cur = cur.next
if cur == None: # 防止后面交換的時(shí)候cur沒有next域
break
pre.next = cur.next # 交換
cur.next = p.next
p.next = cur
p = p.next # 下一次交換做準(zhǔn)備
cur = pre.next
return head
問題描述：【Linked List】445. Add Two Numbers II
解題思路：
這道題是給兩個(gè)鏈表，將兩個(gè)鏈表相加。
使用了一種簡單的做法，就是將兩個(gè)鏈表的值保存在 list 中，然后反向遍歷 list，利用頭插法構(gòu)造新鏈表，將每次計(jì)算的各個(gè)位的結(jié)果保存在新鏈表中即可。這樣時(shí)間復(fù)雜度和空間復(fù)雜度均為 O(n)，代碼如下。
實(shí)際上這道題還可以使用鏈表反轉(zhuǎn)的思想，將兩鏈表反轉(zhuǎn)，然后再求和。這樣空間復(fù)雜度可以做到 O(1)。
Python3 實(shí)現(xiàn)：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
list1, list2 = [], []
head1, head2 = l1, l2
while head1:
list1.append(head1.val)
head1 = head1.next
while head2:
list2.append(head2.val)
head2 = head2.next
i, j, c = len(list1) - 1, len(list2) - 1, 0 # c:進(jìn)位
head = None
while i >= 0 or j >= 0 or c == 1:
add = c
if i >= 0: add += list1[i]
if j >= 0: add += list2[j]
c = add // 10
node = ListNode(add % 10)
node.next = head # 頭插法
head = node
i, j = i - 1, j - 1
return head
問題描述：【Linked List】725. Split Linked List in Parts
解題思路：
這道題是給一個(gè)鏈表和整數(shù) k，將鏈表劃分成長度盡可能相等的 k 個(gè)連續(xù)部分，返回鏈表列表。
首先需要注意，鏈表列表是指一個(gè)列表，列表中每一項(xiàng)是一個(gè)鏈表。這道題根據(jù)鏈表的長度 size （先遍歷一次鏈表）分為兩種情況：
1、size <= k：每段鏈表只有一個(gè)值或者為 None。
2、size > k：通過 div, mod = divmod(size, k) 來計(jì)算每段鏈表中至少應(yīng)該包含 div 個(gè)值，然后將 mod 平均分配到前面每一段鏈表中。
Python3 實(shí)現(xiàn)：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def splitListToParts(self, root: ListNode, k: int) -> List[ListNode]:
cur = root
size = 0 # 鏈表長度
while cur:
size += 1
cur = cur.next
ans = [] # 結(jié)果
if size <= k:
cur = root
for i in range(k):
if i < size:
ans.append(ListNode(cur.val))
cur = cur.next
else:
ans.append(None) # 空鏈表
else:
div, mod = divmod(size, k)
for _ in range(k): # 對于每一段
head = cur = root # head 構(gòu)造每一段鏈表
for _ in range(div - 1): # 注意少循環(huán)一次，防止 cur.next 越界
cur = cur.next
if mod > 0: # 有余數(shù)，平均分配到前面每一段鏈表中
cur = cur.next
mod -= 1
root = cur.next # root 指向剩余的鏈表
cur.next = None # 截?cái)? ans.append(head) # 將每一段鏈表保存
return ans
