总目录
21 合并两个有序链表
返回总目录
题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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
l1
和 l2
均按 非递减顺序 排列
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 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 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 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
函数开头加上以下代码,当 list1
或 list2
为 NULL
时,可以提高效率。(解法三 和 解法四 均包含该段代码。)
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 struct ListNode* mergeTwoLists (struct ListNode* list1, struct ListNode* list2) { struct ListNode *now , *head ; 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 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
操作(忽略边界情况,比如空链表等):
{ l i s t 1 [ 0 ] + m e r g e ( l i s t 1 [ 1 : ] , l i s t 2 ) l i s t 1 [ 0 ] < l i s t 2 [ 0 ] l i s t 2 [ 0 ] + m e r g e ( l i s t 1 , l i s t 2 [ 1 : ] ) o t h e r w i s e \begin{cases}
list1[0]+merge(list1[1:],list2)& \text{$list1[0]<list2[0]$}\\
list2[0]+merge(list1,list2[1:])& \text{$otherwise$}
\end{cases} { l i s t 1 [ 0 ] + m e r g e ( l i s t 1 [ 1 : ] , l i s t 2 ) l i s t 2 [ 0 ] + m e r g e ( l i s t 1 , l i s t 2 [ 1 : ] ) l i s t 1 [ 0 ] < l i s t 2 [ 0 ] o t h er w i se
也就是说,两个链表头部值较小的一个节点与剩下元素的 merge
操作结果合并。
我们直接将以上递归过程建模,同时需要考虑边界情况。
如果 l1
或者 l2
一开始就是空链表 ,那么没有任何操作需要合并,所以我们只需要返回非空链表。否则,我们要判断 l1
和 l2
哪一个链表的头节点的值更小,然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空,递归结束。
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) O ( n + m ) ,其中 n n n 和 m m m 分别为两个链表的长度。因为每次调用递归都会去掉 l1
或者 l2
的头节点(直到至少有一个链表为空),函数 mergeTwoList
至多只会递归调用每个节点一次。因此,时间复杂度取决于合并后的链表长度,即 O ( n + m ) O(n + m) O ( n + m ) 。
空间复杂度:O ( n + m ) O(n + m) O ( n + m ) ,其中 n n n 和 m m m 分别为两个链表的长度。递归调用 mergeTwoLists
函数时需要消耗栈空间,栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists
函数最多调用 n + m n + m n + m 次,因此空间复杂度为 O ( n + m ) O(n + m) O ( n + m ) 。
方法二:迭代
我们可以用迭代的方法来实现上述算法。当 l1
和 l2
都不是空链表时,判断 l1
和 l2
哪一个链表的头节点的值更小,将较小值的节点添加到结果里,当一个节点被添加到结果里之后,将对应链表中的节点向后移一位。
首先,我们设定一个哨兵节点 prehead
,这可以在最后让我们比较容易地返回合并后的链表。我们维护一个 prev
指针,我们需要做的是调整它的 next
指针。然后,我们重复以下过程,直到 l1
或者 l2
指向了 null
:如果 l1
当前节点的值小于等于 l2
,我们就把 l1
当前的节点接在 prev
节点的后面同时将 l1
指针往后移一位。否则,我们对 l2
做同样的操作。不管我们将哪一个元素接在了后面,我们都需要把 prev
向后移一位。
在循环终止的时候, l1
和 l2
至多有一个是非空的。由于输入的两个链表都是有序的,所以不管哪个链表是非空的,它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着我们只需要简单地将非空链表接在合并链表的后面,并返回合并链表即可。
下图展示了 1->4->5
和 1->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; } prev->next = l1 == nullptr ? l2 : l1; return preHead->next; } };
时间复杂度:O ( n + m ) O(n + m) O ( n + m ) ,其中 n n n 和 m m m 分别为两个链表的长度。因为每次循环迭代中,l1
和 l2
只有一个元素会被放进合并链表中, 因此 while
循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的,因此总的时间复杂度为 O ( n + m ) O(n + m) O ( n + m ) 。
空间复杂度:O ( 1 ) 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:
示例 3:
提示:
k = = k == k = = lists.length
0 ≤ k ≤ 1 0 4 0 \leq k \leq 10^4 0 ≤ k ≤ 1 0 4
0 ≤ 0 \leq 0 ≤ lists[i].length
≤ 500 \leq 500 ≤ 5 0 0
− 1 0 4 ≤ -10^4 \leq − 1 0 4 ≤ lists[i][j]
≤ 1 0 4 \leq 10^4 ≤ 1 0 4
lists[i]
按 升序 排列
lists[i].length
的总和不超过 1 0 4 10^4 1 0 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 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; }
官方题解
前置知识:合并两个有序链表
思路
在解决 「 「 「 合并 K K K 个排序链表 」 」 」 这个问题之前,我们先来看一个更简单的问题:如何合并两个有序链表?假设链表 a
和 b
的长度都是 n n n , 如何在 O ( n ) O(n) O ( n ) 的时间代价以及 O ( 1 ) O(1) O ( 1 ) 的空间代价完成合并? 这个问题在面试中常常出现,为了达到空间代价是 O ( 1 ) O(1) O ( 1 ) ,我们的宗旨是 「 「 「 原地调整链表元素的 next
指针完成合并 」 」 」 。 以下是合并的步骤和注意事项,对这个问题比较熟悉的读者可以跳过这一部分。此部分建议结合代码阅读。
首先我们需要一个变量 head
来保存合并之后链表的头部,你可以把 head
设置为一个虚拟的头(也就是 head
的 val
属性不保存任何值),这是为了方便代码的书写,在整个链表合并完之后,返回它的下一位置即可。
我们需要一个指针 tail
来记录下一个插入位置的前一个位置,以及两个指针 aPtr
和 bPtr
来记录 a
和 b
未合并部分的第一位。 注意这里的描述,tail
不是下一个插入的位置,aPtr
和 bPtr
所指向的元素处于「待合并」的状态,也就是说它们还没有合并入最终的链表。 当然你也可以给他们赋予其他的定义,但是定义不同实现就会不同。
当 aPtr
和 bPtr
都不为空的时候,取 val
属性较小的合并;如果 aPtr
为空,则把整个 bPtr
以及后面的元素全部合并;bPtr
为空时同理。
在合并的时候,应该先调整 tail
的 next
属性,再后移 tail
和 *Ptr
(aPtr
或者 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 ( n ) 。
空间复杂度:O ( 1 ) O(1) O ( 1 ) 。
方法一:顺序合并
思路
我们可以想到一种最朴素的方法:用一个变量 ans
来维护已经合并的链表,第 i i i 次循环把第 i i i 个链表和 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; } };
复杂度分析
时间复杂度:假设每个链表的最长长度是 n n n 。在第一次合并后,ans
的长度为 n n n ;第二次合并后,ans
的长度为 2 × n 2 \times n 2 × n ,第 i i i 次合并后,ans
的长度为 i × n i \times n i × n 。第 i i i 次合并的时间代价是 O ( n + ( i − 1 ) × n ) = O ( i × n ) O(n + (i - 1) \times n) = O(i \times n) O ( n + ( i − 1 ) × n ) = O ( i × n ) ,那么总的时间代价为 O ( ∑ i = 1 k ( i × n ) ) = O ( ( 1 + k ) ⋅ k 2 × n ) = O ( k 2 n ) O(\sum_{i = 1}^{k} (i \times n)) = O(\frac{(1 + k)\cdot k}{2} \times n) = O(k^2 n) O ( ∑ i = 1 k ( i × n ) ) = O ( 2 ( 1 + k ) ⋅ k × n ) = O ( k 2 n ) ,故渐进时间复杂度为 O ( k 2 n ) O(k^2 n) O ( k 2 n ) 。
空间复杂度:没有用到与 k k k 和 n n n 规模相关的辅助空间,故渐进空间复杂度为 O ( 1 ) O(1) O ( 1 ) 。
方法二:分治合并
思路
考虑优化方法一,用分治的方法进行合并。
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 ); } };
复杂度分析
时间复杂度:考虑递归 「 「 「 向上回升 」 」 」 的过程 —— 第一轮合并 k 2 \frac{k}{2} 2 k 组链表,每一组的时间代价是 O ( 2 n ) O(2n) O ( 2 n ) ;第二轮合并 k 4 \frac{k}{4} 4 k 组链表,每一组的时间代价是 O ( 4 n ) O(4n) O ( 4 n ) … 所以总的时间代价是 O ( ∑ i = 1 ∞ k 2 i × 2 i n ) = O ( k n × log k ) O(\sum_{i = 1}^{\infty} \frac{k}{2^i} \times 2^i n) = O(kn \times \log k) O ( ∑ i = 1 ∞ 2 i k × 2 i n ) = O ( k n × log k ) ,故渐进时间复杂度为 O ( k n × log k ) O(kn \times \log k) O ( k n × log k ) 。
空间复杂度:递归会使用到 O ( log k ) O(\log k) O ( log k ) 空间代价的栈空间。
方法三:使用优先队列合并
思路
这个方法和前两种方法的思路有所不同,我们需要维护当前每个链表没有被合并的元素的最前面一个,k k k 个链表就最多有 k k k 个满足这样条件的元素,每次在这些元素里面选取 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; } };
复杂度分析
时间复杂度:考虑优先队列中的元素不超过 k k k 个,那么插入和删除的时间代价为 O ( log k ) O(\log k) O ( log k ) ,这里最多有 k n kn k n 个点,对于每个点都被插入删除各一次,故总的时间代价即渐进时间复杂度为 O ( k n × log k ) O(kn \times \log k) O ( k n × log k ) 。
空间复杂度:这里用了优先队列,优先队列中的元素不超过 k k k 个,故渐进空间复杂度为 O ( k ) O(k) O ( k ) 。
1 2 3 4 作者:LeetCode-Solution 链接:https: 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
88 合并两个有序数组
返回总目录
题目描述
给你两个按 非递减顺序 排列的整数数组 nums1
和 nums2
,另有两个整数 m
和 n
,分别表示 nums1
和 nums2
中的元素数目。
请你 合并 nums2
到 nums1
中,使合并后的数组同样按 非递减顺序 排列。
注意: 最终,合并后数组不应由函数返回,而是存储在数组 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 ) l o g ( m + n ) ) O((m + n)log(m + n)) O ( ( m + n ) l o g ( m + n ) ) 。
排序序列长度为 m + n m + n m + n ,套用快速排序的时间复杂度即可,平均情况为 O ( ( m + n ) l o g ( m + n ) ) O((m + n)log(m + n)) O ( ( m + n ) l o g ( m + n ) ) 。
空间复杂度:O ( l o g ( m + n ) ) O(log(m + n)) O ( l o g ( m + n ) ) 。
排序序列长度为 m + n m + n m + n ,套用快速排序的空间复杂度即可,平均情况为 O ( l o g ( m + n ) ) O(log(m + n)) O ( l o g ( m + n ) ) 。
方法二:双指针
方法一没有利用数组 nums1
与 nums2
已经被排序的性质。为了利用这一性质,我们可以使用双指针方法。这一方法将两个数组看作队列,每次从两个数组头部取出比较小的数字放到结果中。如下面的动画所示:打开原网址查看
我们为两个数组分别设置一个指针 p1
与 p2
来作为队列的头部指针。代码实现如下:
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) O ( m + n ) 。
指针移动单调递增,最多移动 m + n m + n m + n 次,因此时间复杂度为 O ( m + n ) O(m + n) O ( m + n ) 。
空间复杂度:O ( m + n ) O(m + n) O ( m + n ) 。
需要建立长度为 m + n m + n m + n 的中间数组 sorted
。
方法三:逆向双指针 (最佳)
方法二中,之所以要使用临时变量,是因为如果直接合并到数组 nums1
中,nums1
中的元素可能会在取出之前被覆盖。那么如何直接避免覆盖 nums1
中的元素呢?观察可知,nums1
的后半部分是空的,可以直接覆盖而不会影响结果。因此可以指针设置为从后向前遍历,每次取两者之中的较大者放进 nums1
的最后面。
严格来说,在此遍历过程中的任意一个时刻,nums1
数组中有 m − p 1 − 1 m - p_1 - 1 m − p 1 − 1 个元素被放入 nums1
的后半部,nums2
数组中有 n − p 2 − 1 n - p_2 - 1 n − p 2 − 1 个元素被放入 nums1
的后半部,而在指针 p1
的后面,nums1
数组有 m + n − p 1 − 1 m + n - p_1 - 1 m + n − p 1 − 1 个位置。由于
m + n − p 1 − 1 ≥ m − p 1 − 1 + n − p 2 − 1 m + n - p_1 - 1 \geq m - p_1 - 1 + n - p_2 - 1
m + n − p 1 − 1 ≥ m − p 1 − 1 + n − p 2 − 1
等价于
p 2 ≥ 1 p_2 \geq 1
p 2 ≥ 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) O ( m + n ) 。
指针移动单调递减,最多移动 m + n m + n m + n 次,因此时间复杂度为 O ( m + n ) O(m + n) O ( m + n ) 。
空间复杂度:O ( 1 ) 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:
提示:
链表中节点的数目在范围 [ 0 , 5 × 1 0 4 ] [0, \; 5 \times 10^4] [ 0 , 5 × 1 0 4 ] 内
− 105 ≤ -105 \leq − 1 0 5 ≤ Node.val
≤ 105 \leq 105 ≤ 1 0 5
进阶: 你可以在 O ( n log n ) O(n \log n) 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 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; }
方法二: 归并排序 (迭代)
官方题解
前言
「 147. 「147. 「 1 4 7 . 对链表进行插入排序 」 」 」 要求使用插入排序的方法对链表进行排序,插入排序的时间复杂度是 O ( n 2 ) O(n^2) O ( n 2 ) ,其中 n n n 是链表的长度。这道题考虑时间复杂度更低的排序算法。题目的进阶问题要求达到 O ( n log n ) O(n \log n) O ( n log n ) 的时间复杂度和 O ( 1 ) O(1) O ( 1 ) 的空间复杂度,时间复杂度是 O ( n log n ) O(n \log n) O ( n log n ) 的排序算法包括归并排序、堆排序和快速排序(快速排序的最差时间复杂度是 O ( n 2 ) O(n^2) O ( n 2 ) ,其中最适合链表的排序算法是 归并排序 。
归并排序基于分治算法。最容易想到的实现方式是自顶向下的递归实现,考虑到递归调用的栈空间,自顶向下归并排序的空间复杂度是 O ( log n ) O(\log n) O ( log n ) 。如果要达到 O ( 1 ) O(1) O ( 1 ) 的空间复杂度,则需要使用自底向上的实现方式。
方法一:自顶向下归并排序
对链表自顶向下归并排序的过程如下。
找到链表的中点,以中点为分界,将链表拆分成两个子链表。寻找链表的中点可以使用 快慢指针 的做法,快指针每次移动 2 2 2 步,慢指针每次移动 1 1 1 步,当快指针到达链表末尾时,慢指针指向的链表节点即为链表的中点。
对两个子链表分别排序。
将两个排序后的子链表合并,得到完整的排序后的链表。可以使用 「 21. 「21. 「 2 1 . 合并两个有序链表 」 」 」 的做法,将两个有序的子链表进行合并。
上述过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于 1 1 1 ,即当链表为空或者链表只包含 1 1 1 个节点时,不需要对链表进行拆分和排序。
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 ( 1 ) O(1) O ( 1 ) 的空间复杂度。
首先求得链表的长度 length
,然后将链表拆分成子链表进行合并。
具体做法如下。
用 subLength
表示每次需要排序的子链表的长度,初始时 subLength
= 1 = 1 = 1 。
每次将链表拆分成若干个长度为 subLength
的子链表(最后一个子链表的长度可以小于 subLength
),按照每两个子链表一组进行合并,合并后即可得到若干个长度为 subLength
× 2 \times 2 × 2 的有序子链表(最后一个子链表的长度可以小于 subLength
× 2 \times 2 × 2 )。合并两个子链表仍然使用 「 21. 「21. 「 2 1 . 合并两个有序链表 」 」 」 的做法。
将 subLength
的值加倍,重复第 2 步,对更长的有序子链表进行合并操作,直到有序子链表的长度大于或等于 length
,整个链表排序完毕。
如何保证每次合并之后得到的子链表都是有序的呢?可以通过数学归纳法证明。
初始时 subLength
= 1 = 1 = 1 ,每个长度为 1 1 1 的子链表都是有序的。
如果每个长度为 subLength
的子链表已经有序,合并两个长度为 subLength
的有序子链表,得到长度为 subLength
× 2 \times 2 × 2 的子链表,一定也是有序的。
当最后一个子链表的长度小于 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; }
复杂度分析
1 2 3 4 作者:LeetCode-Solution 链接:https://leetcode.cn/problems/sort-list/solution/pai-xu-lian-biao-by-leetcode-solution/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
----------------- END -----------------