問題描述：【Linked List】86. Partition List
解題思路：
這道題是給一個(gè)鏈表和整數(shù) x畸悬，將小于 x 的數(shù)按位置順序放在鏈表左側(cè)侧甫，大于等于 x 的按位置順序放在右側(cè)。
類似于快排的劃分過程有木有蹋宦∨冢可以建立兩個(gè)指針 l_end 和 r_end，分別指向 x 的左右兩部分的尾部冷冗。再建立一個(gè)指針指向當(dāng)前結(jié)點(diǎn) cur僻爽，便于鏈表的遍歷。因?yàn)槲覀儾恢赖谝粋€(gè)結(jié)點(diǎn)和 x 的關(guān)系贾惦，所以可以建一個(gè)空結(jié)點(diǎn) node 指向 head胸梆，最后 head.next 就是答案。
- l_end 初始化為 head（空結(jié)點(diǎn)）须板，r_end 初始化為 None碰镜，cur 指向 head.next 第一個(gè)結(jié)點(diǎn)；
- 遍歷 cur：
1习瑰、如果cur.val < x and r_end == None绪颖，說明剛開始碰到的都是小于 x 的，就只需要移動 l_end 到 cur 的位置即可甜奄；
2柠横、 如果cur.val < x，這個(gè)時(shí)候 r_end 不為空课兄，利用這三個(gè)指針進(jìn)行交換和移動即可牍氛；
3、否則烟阐，碰到的都是大于等于 x 的搬俊，就只需要移動 r_end 到 cur 的位置即可紊扬。
時(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 partition(self, head: ListNode, x: int) -> ListNode:
node = ListNode(-1) # 頭結(jié)點(diǎn)
node.next = head
head = node
l_end, r_end, cur = head, None, head.next
while cur:
if cur.val < x and r_end == None: # 沒遇到比 x 大的餐屎，只移動 l_end
l_end = cur
elif cur.val < x: # r_end 不為 None，利用三指針交換
r_end.next = cur.next # 交換
cur.next = l_end.next
l_end.next = cur
l_end = cur # 移動
cur = r_end
else:
r_end = cur
cur = cur.next
return head.next
問題描述：【Linked List】92. Reverse Linked List II
解題思路：
這道題是給一個(gè)鏈表和區(qū)間 [m, n]玩祟，反轉(zhuǎn)區(qū)間內(nèi)的數(shù)字腹缩。
這道題和下面的 Leetcode 206 思路相同。對于一個(gè)區(qū)間的反轉(zhuǎn)空扎，需要用 notr 記錄不用反轉(zhuǎn)區(qū)間的最后一個(gè)位置藏鹊；用 start 記錄反轉(zhuǎn)區(qū)間的頭指針；為了反轉(zhuǎn)方便勺卢，再定義 pre 和 cur 分別為前一個(gè)指針和當(dāng)前指針伙判。遍歷 cur，找到反轉(zhuǎn)區(qū)間黑忱，進(jìn)行指針的交換和移動操作即可宴抚。
時(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 reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
if not head:
return head
# notr: 不用反轉(zhuǎn)區(qū)間的最后一個(gè)位置
# start: 反轉(zhuǎn)區(qū)間的頭指針
# pre, cur：前一個(gè)指針和當(dāng)前指針
notr, start, pre, cur = None, None, None, head
i = 1
while cur:
if i <= m:
if i == m: # 初始化四個(gè)指針
notr = pre
start = cur
pre = cur
cur = cur.next
elif m < i <= n: # 在起始位置的下一個(gè)位置反轉(zhuǎn)菇曲，通過指針交換完成
pre.next = cur.next # 交換
cur.next = start
start = cur
if m == 1: # 從頭開始
head = cur
else: # 從中間開始
notr.next = start
cur = pre.next # 移動
else:
break
i += 1
return head
問題描述：【Linked List】148. Sort List
解題思路：
這道題是給一個(gè)鏈表，對鏈表排序抚吠。要求時(shí)間復(fù)雜度 O(nlogn)常潮，空間復(fù)雜度 O(1)。
首先楷力，肯定能想到要么是使用快速排序喊式，要么是歸并排序。剛好上面的 Leetcode 86 為鏈表劃分萧朝，所以就借助其思想實(shí)現(xiàn)了快排岔留。但是最后一個(gè) case 超時(shí)了（嚶嚶嚶），代碼如下：
Python3 實(shí)現(xiàn)：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def sortList(self, head: ListNode) -> ListNode:
if not head or not head.next: # 遞歸出口
return head
pivot = head.val
le, ri, cur = head, None, head.next # 左右區(qū)間劃分
while cur:
if cur.val < pivot and ri == None:
le = cur
elif cur.val < pivot:
ri.next = cur.next # 交換
cur.next = le.next
le.next = cur
le = cur # 移動
cur = ri
else:
ri = cur
cur = cur.next
ri = le.next # 左右兩側(cè)排序
le.next = None
lp = self.sortList(head.next)
rp = self.sortList(ri)
if lp == None: # 將基準(zhǔn) head.val 放到中間
head.next = rp
lp = head
else:
cur = lp
while cur.next:
cur = cur.next
cur.next = head
head.next = rp
return lp # 返回鏈表頭結(jié)點(diǎn)
看了題解检柬，有人使用歸并排序 mergeSort 通過了献联，同樣可以做到時(shí)間復(fù)雜度為 O(nlogn)，空間復(fù)雜度為 O(1)何址。代碼如下（不是我寫的里逆，懶得再寫一次了）：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def sortList(self, head: ListNode) -> ListNode:
if head is None:
return None
p, i = head, 0
while p:
i += 1
p = p.next
return self.mergeSort(head, i)[0]
def mergeSort(self,head,k):
if k == 1:
next = head.next
head.next = None
return head, next
left_head, next = self.mergeSort(head, k//2)
right_head, next = self.mergeSort(next, k-(k//2))
return self.merge(left_head, right_head), next
def merge(self, h1, h2):
dummy = ListNode(0)
p = dummy
while h1 and h2:
if h1.val <= h2.val:
p.next = h1
p = p.next
h1 = h1.next
else:
p.next = h2
p = p.next
h2 = h2.next
if h1 is None and h2 is not None:
p.next = h2
elif h2 is None and h1 is not None:
p.next = h1
return dummy.next
問題描述：【Linked List】206. Reverse Linked List
解題思路：
這道題是給一個(gè)鏈表，將鏈表反轉(zhuǎn)用爪。
鏈表反轉(zhuǎn)只需要兩個(gè)相鄰指針 pre 和 cur 即可原押。對于 cur 遍歷，先交換（3 次操作）后移動指針到正確的位置项钮，時(shí)間復(fù)雜度為 O(n)班眯。
Python3 實(shí)現(xiàn)：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head:
return head
pre, cur = head, head.next
while cur:
pre.next = cur.next # 交換
cur.next = head
head = cur
cur = pre.next # 移動
return head
