0725-分隔链表

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:26 2023-09-13 16:06:26 Updated    

给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。

这 k 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。

返回一个由上述 k 部分组成的数组。

示例 1：

**输入：** head = [1,2,3], k = 5
**输出：** [[1],[2],[3],[],[]]
**解释：**
第一个元素 output[0] 为 output[0].val = 1 ，output[0].next = null 。
最后一个元素 output[4] 为 null ，但它作为 ListNode 的字符串表示是 [] 。

示例 2：

**输入：** head = [1,2,3,4,5,6,7,8,9,10], k = 3
**输出：** [[1,2,3,4],[5,6,7],[8,9,10]]
**解释：**
输入被分成了几个连续的部分，并且每部分的长度相差不超过 1 。前面部分的长度大于等于后面部分的长度。

提示：

  • 链表中节点的数目在范围 [0, 1000]
  • 0 <= Node.val <= 1000
  • 1 <= k <= 50

方法一：拆分链表

题目要求将给定的链表分隔成 k 个连续的部分。由于分隔成的每个部分的长度和原始链表的长度有关，因此需要首先遍历链表，得到链表的长度 n。

得到链表的长度 n 之后，记 quotient} = \Big\lfloor \dfrac{n}{k} \Big\rfloor，remainder} = n \bmod k，则在分隔成的 k 个部分中，前 remainder 个部分的长度各为 quotient} + 1，其余每个部分的长度各为 quotient。

分隔链表时，从链表的头结点开始遍历，记当前结点为 curr，对于每个部分，进行如下操作：

  1. 将 curr 作为当前部分的头结点；

  2. 计算当前部分的长度 partSize；

  3. 将 curr 向后移动 partSize 步，则 curr 为当前部分的尾结点；

  4. 当 curr 到达当前部分的尾结点时，需要拆分 curr 和后面一个结点之间的连接关系，在拆分之前需要存储 curr 的后一个结点 next；

  5. 令 curr 的 next 指针指向 null，完成 curr 和 next 的拆分；

  6. 将 next 赋值给 curr。

完成上述操作之后，即得到分隔链表后的一个部分。重复上述操作，直到分隔出 k 个部分，或者链表遍历结束，即 curr 指向 null。

[sol1-Java]
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
class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        int n = 0;
        ListNode temp = head;
        while (temp != null) {
            n++;
            temp = temp.next;
        }
        int quotient = n / k, remainder = n % k;

        ListNode[] parts = new ListNode[k];
        ListNode curr = head;
        for (int i = 0; i < k && curr != null; i++) {
            parts[i] = curr;
            int partSize = quotient + (i < remainder ? 1 : 0);
            for (int j = 1; j < partSize; j++) {
                curr = curr.next;
            }
            ListNode next = curr.next;
            curr.next = null;
            curr = next;
        }
        return parts;
    }
}
[sol1-C#]
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
public class Solution {
    public ListNode[] SplitListToParts(ListNode head, int k) {
        int n = 0;
        ListNode temp = head;
        while (temp != null) {
            n++;
            temp = temp.next;
        }
        int quotient = n / k, remainder = n % k;

        ListNode[] parts = new ListNode[k];
        ListNode curr = head;
        for (int i = 0; i < k && curr != null; i++) {
            parts[i] = curr;
            int partSize = quotient + (i < remainder ? 1 : 0);
            for (int j = 1; j < partSize; j++) {
                curr = curr.next;
            }
            ListNode next = curr.next;
            curr.next = null;
            curr = next;
        }
        return parts;
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def splitListToParts(self, head: ListNode, k: int) -> List[ListNode]:
        n = 0
        node = head
        while node:
            n += 1
            node = node.next
        quotient, remainder = n // k, n % k

        parts = [None for _ in range(k)]
        i, curr = 0, head
        while i < k and curr:
            parts[i] = curr
            part_size = quotient + (1 if i < remainder else 0)
            for _ in range(part_size - 1):
                curr = curr.next
            next = curr.next
            curr.next = None
            curr = next
            i += 1
        return parts
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var splitListToParts = function(head, k) {
    let n = 0;
    let temp = head;
    while (temp != null) {
        n++;
        temp = temp.next;
    }
    let quotient = Math.floor(n / k), remainder = n % k;

    const parts = new Array(k).fill(null);
    let curr = head;
    for (let i = 0; i < k && curr != null; i++) {
        parts[i] = curr;
        let partSize = quotient + (i < remainder ? 1 : 0);
        for (let j = 1; j < partSize; j++) {
            curr = curr.next;
        }
        const next = curr.next;
        curr.next = null;
        curr = next;
    }
    return parts;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func splitListToParts(head *ListNode, k int) []*ListNode {
    n := 0
    for node := head; node != nil; node = node.Next {
        n++
    }
    quotient, remainder := n/k, n%k

    parts := make([]*ListNode, k)
    for i, curr := 0, head; i < k && curr != nil; i++ {
        parts[i] = curr
        partSize := quotient
        if i < remainder {
            partSize++
        }
        for j := 1; j < partSize; j++ {
            curr = curr.Next
        }
        curr, curr.Next = curr.Next, nil
    }
    return parts
}
[sol1-C++]
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
class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* head, int k) {
        int n = 0;
        ListNode *temp = head;
        while (temp != nullptr) {
            n++;
            temp = temp->next;
        }
        int quotient = n / k, remainder = n % k;

        vector<ListNode*> parts(k,nullptr);
        ListNode *curr = head;
        for (int i = 0; i < k && curr != nullptr; i++) {
            parts[i] = curr;
            int partSize = quotient + (i < remainder ? 1 : 0);
            for (int j = 1; j < partSize; j++) {
                curr = curr->next;
            }
            ListNode *next = curr->next;
            curr->next = nullptr;
            curr = next;
        }
        return parts;
    }
};

复杂度分析

  • 时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表两次，得到链表的长度和分隔链表。

  • 空间复杂度：O(1)。只使用了常量的额外空间，注意返回值不计入空间复杂度。

 Comments
On this page
0725-分隔链表