725. Split Linked List in Parts

https://leetcode.com/problems/split-linked-list-in-parts/

题目解释

你会得到一组链结串列的头head，还有一个数字k

请把这组链结串列拆成k个链结串列，且要符合下列三个规则

1. 相邻的两段链结串列长度不能超过1个
2. 前面的链结长度必须大於等於後面的链结长度
3. 数字并须要保有原来的顺序

example

解法

我们可以把原本的链结切成k段，或是做出k个新的链结

不论如何我们都需要先知道链结的长度有多长，所以我们先全部轮过一遍找出长度N

接着，我们要找出每一段分别要放几个节点，并符合上面提到的规则

以k=3, N=10作为例子，我们的链结长度就会分别是4,3,3

也就是每个链结长度是N//3，但是前N%3个链结的节点会多一个

知道长度之後我们就知道要在哪断开链结了

程序码

class Solution:
    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:
        
        node = head
        N = 0
        while node:
            N += 1
            node = node.next
        
        D = N // k
        M = N % k
        
        ans = []
        node1, node2 = ListNode(head), head
        # node1是留来断开链结的
        for i in range(M):
            root = node2
            for i in range(D+1):
                if node2:
                    node1 = node2
                    node2 = node2.next
            
            node1.next = None
            ans.append(root)
                
        node1, node2 = ListNode(node2), node2
        for i in range(k - M):
            root = node2
            for i in range(D):
                if node2:
                    node1 = node2
                    node2 = node2.next
            
            node1.next = None
            ans.append(root)
        
        return ans

上面的程序码真的丑

稍微好看一点的版本

class Solution:
    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:
        
        node = head
        N = 0
        while node:
            N += 1
            node = node.next
        
        D = N // k
        M = N % k
        
        size = [D+1] * M + [D] * (k - M)
        ans = []
        
        node = head
        for i in size:
            root = node
            for j in range(i-1):
                if node:
                    node = node.next
                
            ans.append(root)
            if node:
                node.next ,node = None, node.next
        
        return ans

闲聊

链结是一种网罗，我们要断开魂节