題目

給定一個頭結點為 root 的連結串列, 編寫一個函式以將連結串列分隔為 k 個連續的部分。

每部分的長度應該儘可能的相等: 任意兩部分的長度差距不能超過 1，也就是說可能有些部分為 null。

這k個部分應該按照在連結串列中出現的順序進行輸出，並且排在前面的部分的長度應該大於或等於後面的長度。

返回一個符合上述規則的連結串列的列表。

舉例： 1->2->3->4, k = 5 // 5 結果 [ [1], [2], [3], [4], null ]

示例 1：輸入: root = [1, 2, 3], k = 5 輸出: [[1],[2],[3],[],[]]

解釋:輸入輸出各部分都應該是連結串列，而不是陣列。

例如, 輸入的結點 root 的 val= 1, root.next.val = 2, \root.next.next.val = 3, 且 root.next.next.next = null。

第一個輸出 output[0] 是 output[0].val = 1, output[0].next = null。

最後一個元素 output[4] 為 null, 它代表了最後一個部分為空連結串列。

示例 2：輸入: root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3

輸出: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]

解釋:輸入被分成了幾個連續的部分，並且每部分的長度相差不超過1.前面部分的長度大於等於後面部分的長度。

提示:root 的長度範圍： [0, 1000].

輸入的每個節點的大小範圍：[0, 999].

k 的取值範圍： [1, 50].

解題思路分析

1、遍歷；時間複雜度O(n)，空間複雜度O(n)

func splitListToParts(root *ListNode, k int) []*ListNode {	res := make([]*ListNode, 0)	cur := root	length := 0	for cur != nil {		length++		cur = cur.Next	}	a, b := length/k, length%k	for i := 0; i < k; i++ {		node := &ListNode{Next: nil}		temp := node		for j := 0; j < a; j++ {			temp.Next = &ListNode{				Val:  root.Val,				Next: nil,			}			temp = temp.Next			root = root.Next		}		if b > 0 {			temp.Next = &ListNode{				Val:  root.Val,				Next: nil,			}			temp = temp.Next			root = root.Next			b = b - 1		}		res = append(res, node.Next)	}	return res}

2、遍歷；時間複雜度O(n)，空間複雜度O(n)

func splitListToParts(root *ListNode, k int) []*ListNode {	res := make([]*ListNode, 0)	cur := root	length := 0	for cur != nil {		length++		cur = cur.Next	}	a, b := length/k, length%k	for i := 0; i < k; i++ {		if root == nil {			res = append(res, nil)			continue		}		node := root		for j := 1; j < a && root.Next != nil; j++ {			root = root.Next		}		if b > 0 {			root = root.Next			b--		}		temp := root.Next		root.Next = nil		root = temp		res = append(res, node)	}	return res}

總結

Medium題目，連結串列問題，注意指標操作