1. 链表反转
1.1 反转链表
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseList(self, head):
pre = None
cur = head
while cur:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
return pre
1.2 反转链表 II
思路：整体来看，p0 是反转前的第 left 个节点的前一个节点（dummy.next），pre 是反转后的头节点，cur 是当前遍历到的节点。
class Solution:
def reverseBetween(self, head, left, right):
p0 = dummy = ListNode(next=head)
for _ in range(left - 1):
p0 = p0.next
pre = None
cur = p0.next
for _ in range(right - left + 1):
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
p0.next.next = cur
p0.next = pre
return dummy.next
1.3 K 个一组翻转链表
class Solution:
def reverseKGroup(self, head, k):
n = 0
cur = head
while cur:
n += 1
cur = cur.next
p0 = dummy = ListNode(next=head)
pre = None
cur = head
while n >= k:
n -= k
for _ in range(k):
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
nxt = p0.next
nxt.next = cur
p0.next = pre
p0 = nxt
return dummy.next
2. 链表排序
2.1 链表的中间结点
代码：典型的快慢指针。
class Solution:
def middleNode(self, head):
t1 = t2 = head
while t2 and t2.next:
t1 = t1.next
t2 = t2.next.next
return t1
2.2 合并两个有序链表
class Solution:
def mergeTwoLists(self, list1, list2):
dummy = ListNode()
cur = dummy
while list1 and list2:
if list1.val <= list2.val:
cur.next = list1
cur = cur.next
list1 = list1.next
else:
cur.next = list2
cur = cur.next
list2 = list2.next
cur.next = list1 if list1 else list2
return dummy.next
2.3 排序链表（归并排序）
思路：找到链表的中间节点，断开为前后两端，分别排序前后两端，排序后再合并两个有序链表。
class Solution:
def middleNode(self, head):
slow = fast = head
while fast and fast.next:
pre = slow
slow = slow.next
fast = fast.next.next
pre.next = None
return slow
def mergeTwoLists(self, list1, list2):
cur = dummy = ListNode()
while list1 and list2:
if list1.val < list2.val:
cur.next = list1
list1 = list1.next
else:
cur.next = list2
list2 = list2.next
cur = cur.next
cur.next = list1 if list1 else list2
return dummy.next
def sortList(self, head):
if not head or not head.next:
return head
head2 = self.middleNode(head)
head = self.sortList(head)
head2 = self.sortList(head2)
return self.mergeTwoLists(head, head2)
