一、25. K 个一组翻转链表

1.1、206. 反转链表

• py代码

class ListNode:
	def __init__(self, val=0, next= node):
		self.val = val
		self.next = next
class Solution:
	def reverseList(self, head):
		pre = None
		cur = head
		while cur:
			next = cur.next
			cur.next = pre
			pre = cur
			cur = next
		return pre

1.2、92. 反转链表 II

• 思路：
  整体来看，1是反转前的第left个节点（p0.next），pre（4）是反转的后的头节点，cur是当前遍历到的节点下一个（5）。

class Solution:
	def reverseBetween(self, head, left, right):
		p0 = dummy = ListNode(next = head) # 这样一起实例化，p0和dummy永远都是指向同一位置
		for _ in range(left-1):
			p0 = p0.next  # 知道转换的前一个结点
		pre = None
		cur = p0.next     # 当前正在处理的节点
		for _ in range(right-left+1)
			nxt = cur.next
			cur.nxt = pre
			pre = cur
			cur = nxt
		p0.next.next = cur
		p0.next = pre
		return dummy.next

• 代码：

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
		# k个一组处理
		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

二、148. 排序链表

2.1、876. 链表的中间结点

• 代码：这道题典型的快慢指针

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        t1 = t2 = head
        while t2 and t2.next:
            t1 = t1.next
            t2 = t2.next.next
        return t1

2.2、21. 合并两个有序链表

• 代码：

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        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
        if list1:
            cur.next = list1
        else:
            cur.next = list2
        return dummy.next

• 思路1：归并排序
  找到链表的中间节点，断开为前后两端，分别排序前后两端，排序后，再合并两个有序链表。
• 代码1：

class Solution:
    # 876. 链表的中间结点（快慢指针）
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            pre = slow  # 记录 slow 的前一个节点
            slow = slow.next
            fast = fast.next.next
        pre.next = None  # 断开 slow 的前一个节点和 slow 的连接
        return slow

    # 21. 合并两个有序链表（双指针）
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        cur = dummy = ListNode()  # 用哨兵节点简化代码逻辑
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1  # 把 list1 加到新链表中
                list1 = list1.next
            else:  # 注：相等的情况加哪个节点都是可以的
                cur.next = list2  # 把 list2 加到新链表中
                list2 = list2.next
            cur = cur.next
        cur.next = list1 if list1 else list2  # 拼接剩余链表
        return dummy.next

    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 如果链表为空或者只有一个节点，无需排序
        if head is None or head.next is None:
            return head
        # 找到中间节点 head2，并断开 head2 与其前一个节点的连接
        # 比如 head=[4,2,1,3]，那么 middleNode 调用结束后 head=[4,2] head2=[1,3]
        head2 = self.middleNode(head)
        # 分治
        head = self.sortList(head)
        head2 = self.sortList(head2)
        # 合并
        return self.mergeTwoLists(head, head2)