题目呈现如下:
思路介绍:
- 以下AC代码用的是合并K个排序链表相类似的代码,采用哨兵节点,用优先队列维护一个小顶堆.
- 可用递归编程.递归出口:l1为空则返回l2,l2为空则返回l1;递归中间过程为:若l1首元素较大,则next=mergeTwoLists(l1.next,l2),即两个新链表的头节点;若l2首元素较大同理.代码未附.
下附AC代码:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
struct functional {
bool operator() (ListNode* n1,ListNode* n2) {
return n1->val > n2->val; // 构建小根堆,我猜测返回的布尔值的意义是:是否对n1进行down操作与n2调换位置
}
};
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
priority_queue<ListNode*,vector<ListNode*>,functional> pq;
ListNode* dummyHead = new ListNode(0); // 哨兵
ListNode* cur = dummyHead;
if(l1) pq.push(l1);
if(l2) pq.push(l2);
while(!pq.empty()) {
ListNode* nxt = pq.top();
pq.pop();
cur->next = nxt;
cur = cur->next;
if(nxt->next) pq.push(nxt->next);
}
return dummyHead->next;
}
};
附加:
今日和友人一同游玩南通,畅游濠河(甚至'负距离'感受了一下濠河[doge])