725. 分隔链表

Python示例

递归拆分链表

def dfs(root, width, extra, ans):
    if not root: return 
    p = root 
    for i in range(width + int(extra > 0) - 1):
        p = p.next 
    after = p.next 
    p.next = None 
    ans.append(root)
    dfs(after, width, extra - 1, ans)
    return ans 
        
class Solution:
    def splitListToParts(self, root: ListNode, k: int) -> List[ListNode]:
        n = 0 
        p = root
        while p:
            n += 1
            p = p.next 
        width, extra = n // k, n % k

        ans = []
        dfs(root, width, extra, ans)
        for _ in range(k - len(ans)):
            ans.append(None)
        return ans 

非递归拆分链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def splitListToParts(self, root: ListNode, k: int) -> List[ListNode]:
        n = 0 
        p = root
        while p:
            n += 1
            p = p.next 
        width, extra = n // k, n % k

        ans = []
        cur = root 
        for i in range(k):
            head = cur 
            for j in range(width + bool(i < extra) - 1): # cur 自己算一个，所以减 1
                if cur: # 可能存在cur 已经走完了
                    cur = cur.next 
            if cur: # 可能存在cur 已经走完了
                bak = cur.next 
                cur.next = None # 断开
                cur = bak 
            ans.append(head)
        return ans