发表于 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

• LC 题目链接