LeetCode 725. 分隔链表

题目描述

✅ 725. 分隔链表

image-20250416224455601

image-20250416224519644

思路分析

  1. 首先，我们需要计算链表的总长度 length。
  2. 然后，我们可以计算每个部分的基本长度 partSize 和多出来的节点数 extraSize。
  3. 接着，我们遍历链表，将节点分配到每个部分中。对于前 extraSize 个部分，我们多分配一个节点。
  4. 最后，将每个部分的头节点存入结果数组中。

参考代码



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
28
29
30
31
32
33
34
35
36
37



func splitListToParts(head *ListNode, k int) []*ListNode {
	// 计算链表的长度
	length := 0
	for cur := head; cur != nil; cur = cur.Next {
		length++
	}

	// 计算每个部分的基本长度和额外节点数
	partSize := length / k
	extraSize := length % k

	// 创建结果数组
	res := make([]*ListNode, k)
	cur := head

	for i := 0; i < k; i++ {
		res[i] = cur
		// 计算当前部分的长度
		size := partSize
		if i < extraSize {
			size++ // 前面部分多一个节点
		}

		// 遍历当前部分
		for j := 0; j < size && cur != nil; j++ {
			if j == size-1 {
				next := cur.Next
				cur.Next = nil // 断开链表
				cur = next
			} else {
				cur = cur.Next
			}
		}
	}

	return res
}
  • 时间复杂度：O (n)，其中 n 是链表的长度。我们需要遍历链表两次：一次计算长度，一次分隔链表。
  • 空间复杂度：O (k)，用于存储结果数组。

➡️ 点击查看 Java 题解



1



write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/2022/50177091
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！