链接:725. 分隔链表
经典链表题目,思路不难,关键在于写法即代码实现能力上。
假设链表长度为 n
,那么 n%k=a
,则意味着 前 a
段是要多分一个的,而 n/k=b
则意味着每段至少是 b
个。多于的给前 a
段一人一个。
这就是本题最终的抽象问题。
在代码实现上,完全可以枚举段数 k
,确定每段分的个数即可。这样就不用分 k>n
及 k<=n
这两种情况了。将枚举段数的 i
与 n%k=a
进行对应,确定前面多一个的段数长度。注意需要将每段的链表末尾置为 NULL
即可。
整体思路不难,主要写下代码精简,以及 go 语言对链表的操作。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: vector<ListNode*> splitListToParts(ListNode* head, int k) { int n = 0; for (auto p = head; p; p = p->next) n ++ ; vector<ListNode*> res; auto p = head; for (int i = 0; i < k; i ++ ) { int len = n / k; if (i + 1 <= n % k) len ++ ; res.push_back(p); for (int i = 0; i < len - 1; i ++ ) p = p->next; if (p) { // 在此可以简化下,可看官方题解 auto t = p->next; p->next = NULL; p = t; } } return res; } };
go
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func splitListToParts(head *ListNode, k int) []*ListNode { n := 0 for p := head; p != nil; p = p.Next { // 必须是表达式,不能写 p n ++ } p := head // res := []*ListNode{} res := make([]*ListNode, k) for i := 0; i < k; i ++ { len := n / k if i + 1 <= n % k { len ++ } // res = append(res, p) res[i] = p for j := 0; j < len - 1; j ++ { p = p.Next } if p != nil { // 在此可以简化下,可看官方题解 t := p.Next p.Next = nil p = t; } } return res }