iT邦幫忙

2021 iThome 鐵人賽

DAY 29
0
自我挑戰組

每日LeetCode解題紀錄系列 第 29

LeetCode解題 Day29

725. Split Linked List in Parts

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


題目解釋

你會得到一組鏈結串列的頭head,還有一個數字k

請把這組鏈結串列拆成k個鏈結串列,且要符合下列三個規則

  1. 相鄰的兩段鏈結串列長度不能超過1個
  2. 前面的鏈結長度必須大於等於後面的鏈結長度
  3. 數字並須要保有原來的順序

example

https://i.imgur.com/VTTb7PG.png


解法

我們可以把原本的鏈結切成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

上面的程式碼真的醜
https://i.redd.it/etaxo60o8ho41.jpg


稍微好看一點的版本

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

閒聊

鏈結是一種網羅,我們要斷開魂節


上一篇
LeetCode解題 Day28
下一篇
LeetCode解題 Day30
系列文
每日LeetCode解題紀錄30

尚未有邦友留言

立即登入留言