力扣-725.分割链表

评论

题目：
725. Split Linked List in Parts(medium)

1
2
3
Input:
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]

Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.

题目大意：
将一个头结点为root的链表，分割成k个连续的小链表；
其中每部分尽可能相等：任意两部分长度差距不超过1,允许存在null，k部分链表按原顺序输出，并且前面部分长度应大于等于后面长度；
样例如上。

解题思路：
链表有N个结点，分割的链表中每个部分起码都有N/k个结点，而且前N%k部分有一个额外的结点，用个简单的循环计算出N;
对于每个部分，计算出该部分有几个结点curSize = size + ( rem -- > 0 ? 1 :0);再把每部分结点连接起来，成为一个部分。
最后。调整修改每个分割链表中最后结点的next = null.

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Java:
public ListNode[] splitListToParts(ListNode root,int k){
    ListNode[] ret = new ListNode[k];
    ListNode cur = root;
    int N = 0;
    while(cur != null){
        N ++;
        cur = cur.next;
    }
    int size = N / k;
    int rem = N % k;
    cur = root;

    for(int i = 0;i< k && cur != null;i++){
        ret[i] = cur;
        int curSize = size + (rem -- > 0 ? 1 : 0);
        for(int j = 0; j < curSize - 1;j++){
            cur = cur.next;
        }
        ListNode next = cur.next;
        cur.next = null;
        cur = next;
    }
    return ret;
}

Python:

InstantCWeedStudent

个人简介。