[数据结构与算法][M链表] lc725. 分隔链表(模拟+代码优化+代码实现)

1. 题目来源

链接：725. 分隔链表

2. 题目解析

经典链表题目，思路不难，关键在于写法即代码实现能力上。

假设链表长度为 n，那么 n%k=a，则意味着 前 a 段是要多分一个的，而 n/k=b 则意味着每段至少是 b 个。多于的给前 a 段一人一个。

这就是本题最终的抽象问题。

在代码实现上，完全可以枚举段数 k，确定每段分的个数即可。这样就不用分 k>n 及 k<=n 这两种情况了。将枚举段数的 i 与 n%k=a 进行对应，确定前面多一个的段数长度。注意需要将每段的链表末尾置为 NULL 即可。

整体思路不难，主要写下代码精简，以及 go 语言对链表的操作。

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n)$

/**
 * 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
}