JZX轻语：简
LeetCode 725 - 分割链表
发表于2024年04月21日
链表题，首先需要遍历一次得到链表的长度length，然后按k切分链表，如果块i满足i < length % k，则该块的长度为length // k + 1（如果切分不均匀，前面的块比后面的块长）；否则，该块的长度为length // k。遍历的时候，使用两个变量curr和prev分别指向当前节点及前驱节点，当curr刚好指向某个块的头节点，则断开prev和curr的联系，将curr添加到结果列表中，并更新下一个块的头节点索引。
class Solution:
def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:
# 计算链表的长度
length = 0
curr = head
while curr:
length += 1
curr = curr.next
# 每部分至少的长度, 如果切分不均匀, 前面部分的长度为block_min_len + 1
block_min_len = length // k
dummy_head = ListNode(0, head)
prev, curr = dummy_head, head
ans = [None] * k
index = 0 # 当前遍历节点的索引
cur_block = 0 # 当前所处的块号
cur_block_head_index = 0 # 当前块的头节点的索引
while curr:
# 遇到当前块的头节点
if index == cur_block_head_index:
# 和前面的节点断开
ans[cur_block] = curr
prev.next = None
# 计算下一个块的信息
cur_block_head_index += block_min_len + (cur_block < (length % k))
cur_block += 1
if cur_block == k: # 如果已经处在最后一个块的头节点位置了，直接break
break
index += 1
# 更新prev和curr, prev不能简单prev.next, 因为可能会和前面的节点发生了断裂
prev, curr = curr, curr.next
return ans