Datawhale编程实践（LeetCode 腾讯精选练习50）Task5

1.合并K个升序链表https://leetcode-cn.com/problems/merge-k-sorted-lists/

这题是leetcode的一个困难题

这里对将两个升序链表进行合并进行了复习，C++代码如下

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

还学到了优先队列的思想，利用python的heapq模块，通过堆进行优先队列的实现

 1 class ListNode:
 2     def __init__(self, x):
 3         self.val = x
 4         self.next = None
 5 
 6 class Solution:
 7     def mergeKLists(self, lists: List[ListNode]) -> ListNode:
 8         if not lists or len(lists) == 0:
 9             return None
10         import heapq
11         heap = []
12         # 首先 for 嵌套 while 就是将所有元素都取出放入堆中
13         for node in lists:
14             while node:
15                 heapq.heappush(heap, node.val)
16                 node = node.next
17         dummy = ListNode(None)
18         cur = dummy
19         # 依次将堆中的元素取出(因为是小顶堆，所以每次出来的都是目前堆中值最小的元素），然后重新构建一个列表返回
20         while heap:
21             temp_node = ListNode(heappop(heap))
22             cur.next = temp_node
23             cur = temp_node
24         return dummy.next

2.删除排序数组中的重复项https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

3.搜索旋转排序数组https://leetcode-cn.com/problems/search-in-rotated-sorted-array/