leetcode链表之分隔链表

725、分隔链表

题目：

给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。

这 k 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。

返回一个由上述 k 部分组成的数组。

示例1：

输入：head = [1,2,3], k = 5
输出：[[1],[2],[3],[],[]]

示例2：

输入：head = [1,2,3,4,5,6,7,8,9,10], k = 3
输出：[[1,2,3,4],[5,6,7],[8,9,10]]

思路：

先求出链表长度，然后根据链表长度进行分隔

class Solution:
    # 获取链表长度
    def getLength(self, head):
        cur = head
        count = 0
        while cur:
            cur = cur.next
            count += 1
        return count

    def splitListToParts(self, head: ListNode, k: int) -> List[ListNode]:
        if not head: return [None for _ in range(k)]
        length = self.getLength(head)
        # 求出每部分长度，以及多余的数据
        part, remainder = length // k, length % k
        ans = []
        cur = prev = head
        while cur:
            # 如果还有剩余则长度+1，由于这里需要的是分隔结点的前置结点，所以进行减一
            step = (part + (1 if remainder else 0)) - 1
            while cur and step:
                cur = cur.next
                step -= 1
            # 如果还有剩余，就减一
            if remainder > 0: remainder -= 1
            # 如果当前节点不为空，说明还未到尾结点
            if cur:
                # 先记录下个结点的位置，以防指针丢失
                next = cur.next
                cur.next = None
                ans.append(prev)
                cur = prev = next
            else:
                ans.append(prev)
            # 这里每操作一次，将k减一，后续补空操作
            k -= 1
        for i in range(k):
            ans.append(None)
        return ans