0%

LeetCode刷题笔记

总目录

21 合并两个有序链表

返回总目录

题目描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1:

示例1

1
2
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]

示例 2:

1
2
输入:l1 = [], l2 = []
输出:[]

示例 3:

1
2
输入:l1 = [], l2 = [0]
输出:[0]

提示:

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1l2 均按 非递减顺序 排列
1
2
3
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/merge-two-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题解

个人题解

解法一 (AC): 暴力法

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
void insertNode(struct ListNode **head, int val);

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
struct ListNode *new = NULL;

while (list1 != NULL && list2 != NULL)
{
if (list1->val < list2->val)
{
insertNode(&new, list1->val);
list1 = list1->next;
}
else
{
insertNode(&new, list2->val);
list2 = list2->next;
}
}
while (list1 != NULL)
{
insertNode(&new, list1->val);
list1 = list1->next;
}
while (list2 != NULL)
{
insertNode(&new, list2->val);
list2 = list2->next;
}

return new;
}

void insertNode(struct ListNode **head, int val)
{
struct ListNode *p = *head;
struct ListNode *t;
t = (struct ListNode *) malloc (sizeof(struct ListNode));
t->val = val;
t->next = NULL;
if (!(*head))
{
*head = t;
return;
}
while (p->next != NULL)
{
p = p->next;
}
p->next = t;
}

解法一的优化 (AC):

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
void insertNode(struct ListNode **head, struct ListNode **tail, int val);

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
struct ListNode *head = NULL, *tail = NULL;

while (list1 != NULL && list2 != NULL)
{
if (list1->val < list2->val)
{
insertNode(&head, &tail, list1->val);
list1 = list1->next;
}
else
{
insertNode(&head, &tail, list2->val);
list2 = list2->next;
}
}
while (list1 != NULL)
{
insertNode(&head, &tail, list1->val);
list1 = list1->next;
}
while (list2 != NULL)
{
insertNode(&head, &tail, list2->val);
list2 = list2->next;
}

return head;
}

void insertNode(struct ListNode **head, struct ListNode **tail, int val)
{
struct ListNode *p;

p = (struct ListNode *) malloc (sizeof(struct ListNode));
p->val = val;
p->next = NULL;
if (!(*head))
{
*head = p;
*tail = p;
return;
}
(*tail)->next = p;
(*tail) = p;
}

解法二 (AC): 多指针法

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
struct ListNode *pre, *now, *t, *tmp;

pre = NULL;
now = list1;
t = list2;
while (now != NULL && t != NULL)
{
if (t->val > now->val)
{
pre = now;
now = pre->next;
continue;
}
tmp = (struct ListNode *) malloc (sizeof(struct ListNode));
tmp->val = t->val;
tmp->next = now;
if (pre == NULL)
{
list1 = tmp;
}
else
{
pre->next = tmp;
}
pre = tmp;
t = t->next;
}
while (t != NULL)
{
tmp = (struct ListNode *) malloc (sizeof(struct ListNode));
tmp->val = t->val;
tmp->next = NULL;
if (pre == NULL)
{
list1 = tmp;
}
else
{
pre->next = tmp;
}
pre = tmp;
t = t->next;
}

return list1;
}

注: 针对 解法一解法二 ,可在 mergeTwoLists 函数开头加上以下代码,当 list1list2NULL 时,可以提高效率。(解法三解法四 均包含该段代码。)

1
2
3
4
if (!list1 || !list2)
{
return list1 == NULL ? list2 : list1;
}

解法三 (AC): (官方题解迭代法 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
27
28
29
30
31
32
33
34
35
36
37
38
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
struct ListNode *now, *head;

//哨兵结点 (dummy node, 哑结点),作用类似头结点,方便统一处理
head = (struct ListNode *) malloc (sizeof(struct ListNode));
head->next = NULL;
now = head;

while (list1 != NULL && list2 != NULL)
{
if (list1->val < list2->val)
{
now->next = list1;
list1 = list1->next;
}
else
{
now->next = list2;
list2 = list2->next;
}
now = now->next;
}
now->next = list1 == NULL ? list2 : list1;
//对官方题解的改进,防止内存泄漏
struct ListNode *ans = head->next;
free(head);

return ans;
}

解法四 (AC): (官方题解递归法 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
27
28
29
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
if (list1 == NULL)
{
return list2;
}
else if (list2 == NULL)
{
return list1;
}
else if (list1->val < list2->val)
{
list1->next = mergeTwoLists(list1->next, list2);
return list1;
}
else
{
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
}

官方题解

方法一:递归

  • 思路

我们可以如下递归地定义两个链表里的 merge 操作(忽略边界情况,比如空链表等):

{list1[0]+merge(list1[1:],list2)list1[0]<list2[0]list2[0]+merge(list1,list2[1:])otherwise\begin{cases} list1[0]+merge(list1[1:],list2)& \text{$list1[0]<list2[0]$}\\ list2[0]+merge(list1,list2[1:])& \text{$otherwise$} \end{cases}

也就是说,两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并。

  • 算法

我们直接将以上递归过程建模,同时需要考虑边界情况。

如果 l1 或者 l2 一开始就是空链表 ,那么没有任何操作需要合并,所以我们只需要返回非空链表。否则,我们要判断 l1l2 哪一个链表的头节点的值更小,然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空,递归结束。

C++ 版本代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == nullptr) {
return l2;
} else if (l2 == nullptr) {
return l1;
} else if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
};
  • 复杂度分析

时间复杂度:O(n+m)O(n + m),其中 nnmm 分别为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点(直到至少有一个链表为空),函数 mergeTwoList 至多只会递归调用每个节点一次。因此,时间复杂度取决于合并后的链表长度,即 O(n+m)O(n + m)

空间复杂度:O(n+m)O(n + m),其中 nnmm 分别为两个链表的长度。递归调用 mergeTwoLists 函数时需要消耗栈空间,栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n+mn + m 次,因此空间复杂度为 O(n+m)O(n + m)


方法二:迭代

  • 思路

我们可以用迭代的方法来实现上述算法。当 l1l2 都不是空链表时,判断 l1l2 哪一个链表的头节点的值更小,将较小值的节点添加到结果里,当一个节点被添加到结果里之后,将对应链表中的节点向后移一位。

  • 算法

首先,我们设定一个哨兵节点 prehead ,这可以在最后让我们比较容易地返回合并后的链表。我们维护一个 prev 指针,我们需要做的是调整它的 next 指针。然后,我们重复以下过程,直到 l1 或者 l2 指向了 null :如果 l1 当前节点的值小于等于 l2 ,我们就把 l1 当前的节点接在 prev 节点的后面同时将 l1 指针往后移一位。否则,我们对 l2 做同样的操作。不管我们将哪一个元素接在了后面,我们都需要把 prev 向后移一位。

在循环终止的时候, l1l2 至多有一个是非空的。由于输入的两个链表都是有序的,所以不管哪个链表是非空的,它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着我们只需要简单地将非空链表接在合并链表的后面,并返回合并链表即可。

下图展示了 1->4->51->2->3->6 两个链表迭代合并的过程:打开原网址查看

C++ 版本代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* preHead = new ListNode(-1);

ListNode* prev = preHead;
while (l1 != nullptr && l2 != nullptr) {
if (l1->val < l2->val) {
prev->next = l1;
l1 = l1->next;
} else {
prev->next = l2;
l2 = l2->next;
}
prev = prev->next;
}

// 合并后 l1 和 l2 最多只有一个还未被合并完,我们直接将链表末尾指向未合并完的链表即可
prev->next = l1 == nullptr ? l2 : l1;

return preHead->next;
}
};
  • 复杂度分析

时间复杂度:O(n+m)O(n + m),其中 nnmm 分别为两个链表的长度。因为每次循环迭代中,l1l2 只有一个元素会被放进合并链表中, 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的,因此总的时间复杂度为 O(n+m)O(n + m)

空间复杂度:O(1)O(1)。我们只需要常数的空间存放若干变量。

1
2
3
4
作者:LeetCode-Solution
链接:https://leetcode.cn/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。



23 合并 k 个升序链表

返回总目录

题目描述

给你一个链表数组,每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中,返回合并后的链表。

示例 1:

1
2
3
4
5
6
7
8
9
10
输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下:
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2:

1
2
输入:lists = []
输出:[]

示例 3:

1
2
输入:lists = [[]]
输出:[]

提示:

  • k==k == lists.length
  • 0k1040 \leq k \leq 10^4
  • 00 \leq lists[i].length 500\leq 500
  • 104-10^4 \leq lists[i][j] 104\leq 10^4
  • lists[i]升序 排列
  • lists[i].length 的总和不超过 10410^4
1
2
3
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/merge-k-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题解

个人题解

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
38
39
40
41
42
43
44
/**
* Definition for singly-linked list.
* struct ListNode
*{
* int val;
* struct ListNode *next;
* };
*/


struct ListNode *mergeKLists(struct ListNode **lists, int listsSize)
{
if (listsSize <= 1)
{
return listsSize == 0 ? NULL : lists[0];
}
struct ListNode *head, *cur, *ans;
head = (struct ListNode *) malloc (sizeof(struct ListNode));
head->next = NULL;
for (int i = 0; i < listsSize - 1; i++)
{
cur = head;
while (lists[i] != NULL && lists[i + 1] != NULL)
{
if (lists[i]->val < lists[i + 1]->val)
{
cur->next = lists[i];
lists[i] = lists[i]->next;
}
else
{
cur->next = lists[i + 1];
lists[i + 1] = lists[i + 1]->next;
}
cur = cur->next;
}
cur->next = lists[i] == NULL ? lists[i + 1] : lists[i];
lists[i + 1] = head->next;
}
ans = head->next;
free(head);

return ans;
}

官方题解

前置知识:合并两个有序链表

思路

在解决 合并 KK 个排序链表 这个问题之前,我们先来看一个更简单的问题:如何合并两个有序链表?假设链表 ab的长度都是 nn如何在 O(n)O(n) 的时间代价以及 O(1)O(1) 的空间代价完成合并? 这个问题在面试中常常出现,为了达到空间代价是 O(1)O(1),我们的宗旨是 原地调整链表元素的 next 指针完成合并 以下是合并的步骤和注意事项,对这个问题比较熟悉的读者可以跳过这一部分。此部分建议结合代码阅读。

首先我们需要一个变量 head 来保存合并之后链表的头部,你可以把 head 设置为一个虚拟的头(也就是 headval 属性不保存任何值),这是为了方便代码的书写,在整个链表合并完之后,返回它的下一位置即可。

我们需要一个指针 tail 来记录下一个插入位置的前一个位置,以及两个指针 aPtrbPtr 来记录 ab 未合并部分的第一位。 注意这里的描述,tail 不是下一个插入的位置,aPtrbPtr 所指向的元素处于「待合并」的状态,也就是说它们还没有合并入最终的链表。 当然你也可以给他们赋予其他的定义,但是定义不同实现就会不同。

aPtrbPtr 都不为空的时候,取 val 属性较小的合并;如果 aPtr 为空,则把整个 bPtr 以及后面的元素全部合并;bPtr 为空时同理。

在合并的时候,应该先调整 tailnext 属性,再后移 tail*PtraPtr 或者 bPtr)。那么这里 tail*Ptr 是否存在先后顺序呢?它们谁先动谁后动都是一样的,不会改变任何元素的 next 指针。

C++ 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
if ((!a) || (!b)) return a ? a : b;
ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
while (aPtr && bPtr) {
if (aPtr->val < bPtr->val) {
tail->next = aPtr; aPtr = aPtr->next;
} else {
tail->next = bPtr; bPtr = bPtr->next;
}
tail = tail->next;
}
tail->next = (aPtr ? aPtr : bPtr);
return head.next;
}

复杂度分析

  • 时间复杂度:O(n)O(n)
  • 空间复杂度:O(1)O(1)

方法一:顺序合并

思路

我们可以想到一种最朴素的方法:用一个变量 ans 来维护已经合并的链表,第 ii 次循环把第 ii 个链表和 ans 合并,答案保存到 ans 中。

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
class Solution {
public:
ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
if ((!a) || (!b)) return a ? a : b;
ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
while (aPtr && bPtr) {
if (aPtr->val < bPtr->val) {
tail->next = aPtr; aPtr = aPtr->next;
} else {
tail->next = bPtr; bPtr = bPtr->next;
}
tail = tail->next;
}
tail->next = (aPtr ? aPtr : bPtr);
return head.next;
}

ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode *ans = nullptr;
for (size_t i = 0; i < lists.size(); ++i) {
ans = mergeTwoLists(ans, lists[i]);
}
return ans;
}
};

复杂度分析

  • 时间复杂度:假设每个链表的最长长度是 nn 。在第一次合并后,ans 的长度为 nn ;第二次合并后,ans 的长度为 2×n2 \times n,第 ii 次合并后,ans 的长度为 i×ni \times n 。第 ii 次合并的时间代价是 O(n+(i1)×n)=O(i×n)O(n + (i - 1) \times n) = O(i \times n) ,那么总的时间代价为 O(i=1k(i×n))=O((1+k)k2×n)=O(k2n)O(\sum_{i = 1}^{k} (i \times n)) = O(\frac{(1 + k)\cdot k}{2} \times n) = O(k^2 n) ,故渐进时间复杂度为 O(k2n)O(k^2 n)

  • 空间复杂度:没有用到与 kknn 规模相关的辅助空间,故渐进空间复杂度为 O(1)O(1)


方法二:分治合并

思路

考虑优化方法一,用分治的方法进行合并。

  • kk 个链表配对并将同一对中的链表合并;

  • 第一轮合并以后, kk 个链表被合并成了 k22\frac{k}{2} 2 个链表,平均长度为 2nk\frac{2n}{k} ,然后是 k4\frac{k}{4} 个链表, k8\frac{k}{8} 个链表等等;

  • 重复这一过程,直到我们得到了最终的有序链表。

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
27
28
class Solution {
public:
ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
if ((!a) || (!b)) return a ? a : b;
ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
while (aPtr && bPtr) {
if (aPtr->val < bPtr->val) {
tail->next = aPtr; aPtr = aPtr->next;
} else {
tail->next = bPtr; bPtr = bPtr->next;
}
tail = tail->next;
}
tail->next = (aPtr ? aPtr : bPtr);
return head.next;
}

ListNode* merge(vector <ListNode*> &lists, int l, int r) {
if (l == r) return lists[l];
if (l > r) return nullptr;
int mid = (l + r) >> 1;
return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
}

ListNode* mergeKLists(vector<ListNode*>& lists) {
return merge(lists, 0, lists.size() - 1);
}
};

复杂度分析

  • 时间复杂度:考虑递归 向上回升 的过程 —— 第一轮合并 k2\frac{k}{2} 组链表,每一组的时间代价是 O(2n)O(2n) ;第二轮合并 k4\frac{k}{4} 组链表,每一组的时间代价是 O(4n)O(4n) … 所以总的时间代价是 O(i=1k2i×2in)=O(kn×logk)O(\sum_{i = 1}^{\infty} \frac{k}{2^i} \times 2^i n) = O(kn \times \log k) ,故渐进时间复杂度为 O(kn×logk)O(kn \times \log k)

  • 空间复杂度:递归会使用到 O(logk)O(\log k) 空间代价的栈空间。


方法三:使用优先队列合并

思路

这个方法和前两种方法的思路有所不同,我们需要维护当前每个链表没有被合并的元素的最前面一个,kk 个链表就最多有 kk 个满足这样条件的元素,每次在这些元素里面选取 val 属性最小的元素合并到答案中。在选取最小元素的时候,我们可以用优先队列来优化这个过程。

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:
struct Status {
int val;
ListNode *ptr;
bool operator < (const Status &rhs) const {
return val > rhs.val;
}
};

priority_queue <Status> q;

ListNode* mergeKLists(vector<ListNode*>& lists) {
for (auto node: lists) {
if (node) q.push({node->val, node});
}
ListNode head, *tail = &head;
while (!q.empty()) {
auto f = q.top(); q.pop();
tail->next = f.ptr;
tail = tail->next;
if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});
}
return head.next;
}
};

复杂度分析

  • 时间复杂度:考虑优先队列中的元素不超过 kk 个,那么插入和删除的时间代价为 O(logk)O(\log k) ,这里最多有 knkn 个点,对于每个点都被插入删除各一次,故总的时间代价即渐进时间复杂度为 O(kn×logk)O(kn \times \log k)

  • 空间复杂度:这里用了优先队列,优先队列中的元素不超过 kk 个,故渐进空间复杂度为 O(k)O(k)

1
2
3
4
作者:LeetCode-Solution
链接:https://leetcode.cn/problems/merge-k-sorted-lists/solution/he-bing-kge-pai-xu-lian-biao-by-leetcode-solutio-2/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。



88 合并两个有序数组

返回总目录

题目描述

给你两个按 非递减顺序 排列的整数数组 nums1nums2 ,另有两个整数 mn ,分别表示 nums1nums2 中的元素数目。

请你 合并 nums2nums1 中,使合并后的数组同样按 非递减顺序 排列。

注意: 最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n ,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n

示例 1:

1
2
3
4
输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出:[1,2,2,3,5,6]
解释:需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ,其中斜体加粗标注的为 nums1 中的元素。

示例 2:

1
2
3
4
输入:nums1 = [1], m = 1, nums2 = [], n = 0
输出:[1]
解释:需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3:

1
2
3
4
5
输入:nums1 = [0], m = 0, nums2 = [1], n = 1
输出:[1]
解释:需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意,因为 m = 0 ,所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示:

  • nums1.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • 1 <= m + n <= 200
  • -109 <= nums1[i], nums2[j] <= 109

进阶: 你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗?

1
2
3
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/merge-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题解

个人题解

插入法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void merge(int *nums1, int nums1Size, int m, int *nums2, int nums2Size, int n)
{
int idx1 = 0, idx2 = 0;

while (idx1 < m && idx2 < n)
{
if (nums2[idx2] > nums1[idx1])
{
idx1++;
continue;
}
for (int i = m - 1; i >= idx1; i--)
{
nums1[i + 1] = nums1[i];
}
nums1[idx1] = nums2[idx2];
idx2++;
m++;
}
while (idx2 < n)
{
nums1[idx1++] = nums2[idx2++];
}
}

官方题解

方法一:直接合并后排序

  • 算法

最直观的方法是先将数组 nums2 放进数组 nums1 的尾部,然后直接对整个数组进行排序。

1
2
3
4
5
6
7
8
9
10
int cmp(int* a, int* b) {
return *a - *b;
}

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
for (int i = 0; i != n; ++i) {
nums1[m + i] = nums2[i];
}
qsort(nums1, nums1Size, sizeof(int), cmp);
}
  • 复杂度分析

时间复杂度:O((m+n)log(m+n))O((m + n)log(m + n))。 排序序列长度为 m+nm + n,套用快速排序的时间复杂度即可,平均情况为 O((m+n)log(m+n))O((m + n)log(m + n))

空间复杂度:O(log(m+n))O(log(m + n))。 排序序列长度为 m+nm + n,套用快速排序的空间复杂度即可,平均情况为 O(log(m+n))O(log(m + n))


方法二:双指针

  • 算法

方法一没有利用数组 nums1nums2 已经被排序的性质。为了利用这一性质,我们可以使用双指针方法。这一方法将两个数组看作队列,每次从两个数组头部取出比较小的数字放到结果中。如下面的动画所示:打开原网址查看

我们为两个数组分别设置一个指针 p1p2 来作为队列的头部指针。代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
int p1 = 0, p2 = 0;
int sorted[m + n];
int cur;
while (p1 < m || p2 < n) {
if (p1 == m) {
cur = nums2[p2++];
} else if (p2 == n) {
cur = nums1[p1++];
} else if (nums1[p1] < nums2[p2]) {
cur = nums1[p1++];
} else {
cur = nums2[p2++];
}
sorted[p1 + p2 - 1] = cur;
}
for (int i = 0; i != m + n; ++i) {
nums1[i] = sorted[i];
}
}
  • 复杂度分析

时间复杂度:O(m+n)O(m + n)。 指针移动单调递增,最多移动 m+nm + n 次,因此时间复杂度为 O(m+n)O(m + n)

空间复杂度:O(m+n)O(m + n)。 需要建立长度为 m+nm + n 的中间数组 sorted


方法三:逆向双指针 (最佳)

  • 算法

方法二中,之所以要使用临时变量,是因为如果直接合并到数组 nums1 中,nums1 中的元素可能会在取出之前被覆盖。那么如何直接避免覆盖 nums1 中的元素呢?观察可知,nums1 的后半部分是空的,可以直接覆盖而不会影响结果。因此可以指针设置为从后向前遍历,每次取两者之中的较大者放进 nums1 的最后面。

严格来说,在此遍历过程中的任意一个时刻,nums1 数组中有 mp11m - p_1 - 1 个元素被放入 nums1 的后半部,nums2 数组中有 np21n - p_2 - 1 个元素被放入 nums1 的后半部,而在指针 p1 的后面,nums1 数组有 m+np11m + n - p_1 - 1 个位置。由于

m+np11mp11+np21m + n - p_1 - 1 \geq m - p_1 - 1 + n - p_2 - 1

等价于

p21p_2 \geq 1

永远成立,因此 p1 后面的位置永远足够容纳被插入的元素,不会产生 p1 的元素被覆盖的情况。

实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
int p1 = m - 1, p2 = n - 1;
int tail = m + n - 1;
int cur;
while (p1 >= 0 || p2 >= 0) {
if (p1 == -1) {
cur = nums2[p2--];
} else if (p2 == -1) {
cur = nums1[p1--];
} else if (nums1[p1] > nums2[p2]) {
cur = nums1[p1--];
} else {
cur = nums2[p2--];
}
nums1[tail--] = cur;
}
}

注:p2 == -1 ,即 nums2 中元素已全部塞到 nums1 中,这时的 nums1 就是最终答案,不用再将 nums1 剩余的值塞到自己当中。因此,将

1
2
3
else if (p2 == -1) {
cur = nums1[p1--];
}

改为

1
2
3
4
else if (p2 == -1)
{
break;
}

可提高效率。

  • 复杂度分析

时间复杂度:O(m+n)O(m + n)。 指针移动单调递减,最多移动 m+nm + n 次,因此时间复杂度为 O(m+n)O(m + n)

空间复杂度:O(1)O(1)。 直接对数组 nums1 原地修改,不需要额外空间。

1
2
3
4
作者:LeetCode-Solution
链接:https://leetcode.cn/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-by-leetco-rrb0/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。



148 排序链表

返回总目录

题目描述

给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表

示例 1:

1
2
输入:head = [4,2,1,3]
输出:[1,2,3,4]

示例 2:

1
2
输入:head = [-1,5,3,4,0]
输出:[-1,0,3,4,5]

示例 3:

1
2
输入:head = []
输出:[]

提示:

  • 链表中节点的数目在范围 [0,  5×104][0, \; 5 \times 10^4] 内
  • 105 -105 \leq Node.val 105\leq 105

进阶: 你可以在 O(nlogn)O(n \log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?

1
2
3
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/sort-list
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题解

个人题解

方法一 (TLE): 冒泡排序

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
38
/**
* Definition for singly-linked list.
* struct ListNode
*{
* int val;
* struct ListNode *next;
* };
*/


struct ListNode* sortList(struct ListNode *head)
{
if (head == NULL || (head && head->next == NULL))
{
return head;
}

struct ListNode *p, *q, *tail = NULL;

while (head != tail)
{
p = head, q = head->next;
while (q != tail)
{
if (p->val > q->val)
{
int t = p->val;
p->val = q->val;
q->val = t;
}
p = q;
q = q->next;
}
tail = p;
}

return head;
}

方法二: 归并排序 (迭代)

1


官方题解

前言

147.「147. 对链表进行插入排序 要求使用插入排序的方法对链表进行排序,插入排序的时间复杂度是 O(n2)O(n^2) ,其中 nn 是链表的长度。这道题考虑时间复杂度更低的排序算法。题目的进阶问题要求达到 O(nlogn)O(n \log n) 的时间复杂度和 O(1)O(1) 的空间复杂度,时间复杂度是 O(nlogn)O(n \log n) 的排序算法包括归并排序、堆排序和快速排序(快速排序的最差时间复杂度是 O(n2)O(n^2) ,其中最适合链表的排序算法是 归并排序

归并排序基于分治算法。最容易想到的实现方式是自顶向下的递归实现,考虑到递归调用的栈空间,自顶向下归并排序的空间复杂度是 O(logn)O(\log n) 。如果要达到 O(1)O(1) 的空间复杂度,则需要使用自底向上的实现方式。

方法一:自顶向下归并排序

对链表自顶向下归并排序的过程如下。

  1. 找到链表的中点,以中点为分界,将链表拆分成两个子链表。寻找链表的中点可以使用 快慢指针 的做法,快指针每次移动 22 步,慢指针每次移动 11 步,当快指针到达链表末尾时,慢指针指向的链表节点即为链表的中点。

  2. 对两个子链表分别排序。

  3. 将两个排序后的子链表合并,得到完整的排序后的链表。可以使用 21.「21. 合并两个有序链表 的做法,将两个有序的子链表进行合并。

上述过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于 11,即当链表为空或者链表只包含 11 个节点时,不需要对链表进行拆分和排序。

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
struct ListNode* merge(struct ListNode* head1, struct ListNode* head2) {
struct ListNode* dummyHead = malloc(sizeof(struct ListNode));
dummyHead->val = 0;
struct ListNode *temp = dummyHead, *temp1 = head1, *temp2 = head2;
while (temp1 != NULL && temp2 != NULL) {
if (temp1->val <= temp2->val) {
temp->next = temp1;
temp1 = temp1->next;
} else {
temp->next = temp2;
temp2 = temp2->next;
}
temp = temp->next;
}
if (temp1 != NULL) {
temp->next = temp1;
} else if (temp2 != NULL) {
temp->next = temp2;
}
return dummyHead->next;
}

struct ListNode* toSortList(struct ListNode* head, struct ListNode* tail) {
if (head == NULL) {
return head;
}
if (head->next == tail) {
head->next = NULL;
return head;
}
struct ListNode *slow = head, *fast = head;
while (fast != tail) {
slow = slow->next;
fast = fast->next;
if (fast != tail) {
fast = fast->next;
}
}
struct ListNode* mid = slow;
return merge(toSortList(head, mid), toSortList(mid, tail));
}

struct ListNode* sortList(struct ListNode* head) {
return toSortList(head, NULL);
}

复杂度分析

  • 时间复杂度:O(nlogn)O(n \log n) ,其中 nn 是链表的长度。

  • 空间复杂度:O(logn)O(\log n),其中 nn 是链表的长度。空间复杂度主要取决于递归调用的栈空间。


方法二:自底向上归并排序

使用自底向上的方法实现归并排序,则可以达到 O(1)O(1) 的空间复杂度。

首先求得链表的长度 length ,然后将链表拆分成子链表进行合并。

具体做法如下。

subLength 表示每次需要排序的子链表的长度,初始时 subLength =1= 1

每次将链表拆分成若干个长度为 subLength 的子链表(最后一个子链表的长度可以小于 subLength),按照每两个子链表一组进行合并,合并后即可得到若干个长度为 subLength ×2\times 2 的有序子链表(最后一个子链表的长度可以小于 subLength ×2\times 2)。合并两个子链表仍然使用 21.「21. 合并两个有序链表 的做法。

subLength 的值加倍,重复第 2 步,对更长的有序子链表进行合并操作,直到有序子链表的长度大于或等于 length,整个链表排序完毕。

如何保证每次合并之后得到的子链表都是有序的呢?可以通过数学归纳法证明。

  1. 初始时 subLength =1= 1 ,每个长度为 11 的子链表都是有序的。

  2. 如果每个长度为 subLength 的子链表已经有序,合并两个长度为 subLength 的有序子链表,得到长度为 subLength ×2\times 2 的子链表,一定也是有序的。

  3. 当最后一个子链表的长度小于 subLength 时,该子链表也是有序的,合并两个有序子链表之后得到的子链表一定也是有序的。

因此可以保证最后得到的链表是有序的。

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
struct ListNode* merge(struct ListNode* head1, struct ListNode* head2) {
struct ListNode* dummyHead = malloc(sizeof(struct ListNode));
dummyHead->val = 0;
struct ListNode *temp = dummyHead, *temp1 = head1, *temp2 = head2;
while (temp1 != NULL && temp2 != NULL) {
if (temp1->val <= temp2->val) {
temp->next = temp1;
temp1 = temp1->next;
} else {
temp->next = temp2;
temp2 = temp2->next;
}
temp = temp->next;
}
if (temp1 != NULL) {
temp->next = temp1;
} else if (temp2 != NULL) {
temp->next = temp2;
}
return dummyHead->next;
}

struct ListNode* sortList(struct ListNode* head) {
if (head == NULL) {
return head;
}
int length = 0;
struct ListNode* node = head;
while (node != NULL) {
length++;
node = node->next;
}
struct ListNode* dummyHead = malloc(sizeof(struct ListNode));
dummyHead->next = head;
for (int subLength = 1; subLength < length; subLength <<= 1) {
struct ListNode *prev = dummyHead, *curr = dummyHead->next;
while (curr != NULL) {
struct ListNode* head1 = curr;
for (int i = 1; i < subLength && curr->next != NULL; i++) {
curr = curr->next;
}
struct ListNode* head2 = curr->next;
curr->next = NULL;
curr = head2;
for (int i = 1; i < subLength && curr != NULL && curr->next != NULL;
i++) {
curr = curr->next;
}
struct ListNode* next = NULL;
if (curr != NULL) {
next = curr->next;
curr->next = NULL;
}
struct ListNode* merged = merge(head1, head2);
prev->next = merged;
while (prev->next != NULL) {
prev = prev->next;
}
curr = next;
}
}
return dummyHead->next;
}

复杂度分析

  • 时间复杂度:O(nlogn)O(n \log n),其中 nn 是链表的长度。

  • 空间复杂度:O(1)O(1)

1
2
3
4
作者:LeetCode-Solution
链接:https://leetcode.cn/problems/sort-list/solution/pai-xu-lian-biao-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。



----------------- END -----------------