問題描述：【Linked List、Recursion】24. Swap Nodes in Pairs
解題思路：
這道題是給一個鏈表罩抗，相鄰結(jié)點數(shù)值兩兩進行交換拉庵，要求不修改結(jié)點值且只能操作鏈表本身。
方法1：三指針完成交換
鏈表中一般涉及兩個結(jié)點交換的操作套蒂，基本上需要相鄰的三個指針 pre1钞支，pre2茫蛹，cur 完成三次交換操作，然后再移動三個指針到下一個正確的位置烁挟。
因此婴洼，我們只需要循環(huán) cur 的位置，往后一直遍歷直到鏈表為空為止信夫。
在這道題中窃蹋，因為是兩兩交換，所以方便的解法就是建立一個空給點 node静稻，作為鏈表的頭結(jié)點 head警没，最后返回的 head.next 就是答案。
注意在交換的過程中振湾，每次交換的三個操作要保證鏈表不能斷杀迹。
時間復(fù)雜度 O(n)，空間復(fù)雜度 O(1)押搪。
Python3 實現(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) # 頭部插入一個空結(jié)點
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：遞歸
這道題實際上還可以使用遞歸（只不過不太好想树酪，看了別人的代碼才恍然大悟）。
1大州、函數(shù)的返回值：交換后的鏈表的頭結(jié)點 head续语。
2、遞歸函數(shù)做了什么：假設(shè) 1->2->3->4->5->...厦画，遞歸函數(shù)完成了 3->4->5... 的交換 swapPairs(head.next.next)疮茄，并返回了指向 4 的 head，因此需要建一個 second 指向 2根暑，然后將 head.next 指向遞歸函數(shù)的返回值力试，并將 second 作為頭結(jié)點 head，最后返回 second排嫌。
3畸裳、遞歸出口：如果鏈表為空或者 head.next 為空，就之間返回 head淳地。
總之怖糊，你不用去想遞歸函數(shù) swapPairs() 后面的交換是怎么完成的，只需要知道它能夠完成交換即可（或許這就是遞歸的精髓吧）颇象。
時間復(fù)雜度 O(n)蓬抄，空間復(fù)雜度 O(1)。
Python3 實現(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
解題思路：
這道題是給一個有序鏈表嚷缭，將其轉(zhuǎn)化為高度平衡的二叉搜索樹。
要將有序鏈表轉(zhuǎn)化為高度平衡的二叉搜索樹，就需要從鏈表的中間斷開阅爽，然后對于左右鏈表就行遞歸調(diào)用即可路幸。具體細(xì)節(jié)：
1、鏈表查找中間點可以通過快慢指針來操作付翁。
2简肴、找到中點后，要以中點的值建立一個樹的根結(jié)點百侧，再把原鏈表斷開砰识，分為前后兩個鏈表，都不能包含原中結(jié)點佣渴，然后再分別對這兩個鏈表遞歸調(diào)用原函數(shù)辫狼，分別連上左右子結(jié)點即可。
時間復(fù)雜度為 O(nlogn)辛润，空間復(fù)雜度為 O(1)膨处。
Python3 實現(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 的前一個結(jié)點，便于斷開左右鏈表
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
解題思路：
這道題是給一個鏈表砂竖，將奇數(shù)位置的數(shù)按位置順序排在鏈表前面真椿，偶數(shù)位置的數(shù)按位置順序排在鏈表后面。要求空間復(fù)雜度 O(1)乎澄，時間復(fù)雜度 O(n)突硝。
設(shè)置三個指針，一個指向奇數(shù)尾部的指針 p置济，一個指向當(dāng)前結(jié)點 cur解恰，一個指向當(dāng)前結(jié)點的前一個結(jié)點 pre。遍歷 cur 的過程中交換三個指針的指向舟肉，然后再移動它們到下一個正確的位置即可。
Python3 實現(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é)點, pre: cur的前一個結(jié)點
cur = head.next # 當(dāng)前結(jié)點
while cur:
pre = pre.next
cur = cur.next
if cur == None: # 防止后面交換的時候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
解題思路：
這道題是給兩個鏈表查库，將兩個鏈表相加路媚。
使用了一種簡單的做法，就是將兩個鏈表的值保存在 list 中翠语，然后反向遍歷 list唇跨，利用頭插法構(gòu)造新鏈表款咖，將每次計算的各個位的結(jié)果保存在新鏈表中即可。這樣時間復(fù)雜度和空間復(fù)雜度均為 O(n)裤园，代碼如下。
實際上這道題還可以使用鏈表反轉(zhuǎn)的思想剂府，將兩鏈表反轉(zhuǎn)拧揽，然后再求和。這樣空間復(fù)雜度可以做到 O(1)。
Python3 實現(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:進位
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
解題思路：
這道題是給一個鏈表和整數(shù) k淤袜，將鏈表劃分成長度盡可能相等的 k 個連續(xù)部分痒谴，返回鏈表列表。
首先需要注意铡羡，鏈表列表是指一個列表积蔚，列表中每一項是一個鏈表。這道題根據(jù)鏈表的長度 size （先遍歷一次鏈表）分為兩種情況：
1烦周、size <= k：每段鏈表只有一個值或者為 None尽爆。
2、size > k：通過 div, mod = divmod(size, k) 來計算每段鏈表中至少應(yīng)該包含 div 個值读慎，然后將 mod 平均分配到前面每一段鏈表中漱贱。
Python3 實現(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 # 截斷
ans.append(head) # 將每一段鏈表保存
return ans
