-
21. 合并两个有序链表 - 力扣(LeetCode)
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode* head=new ListNode; ListNode* p=head; ListNode* res=head; while(list1 && list2){ if(list1->val<=list2->val){ ListNode* temp=new ListNode; p->next=temp; temp->val=list1->val; p=p->next; list1=list1->next; } else{ ListNode* temp=new ListNode; p->next=temp; temp->val=list2->val; p=p->next; list2=list2->next; } } if(list1==nullptr && list2!=nullptr){ p->next=list2; } else if(list1!=nullptr && list2==nullptr){ p->next=list1; } return res->next; } };
总结:当你需要创造一条新链表的时候,可以使用虚拟头结点简化边界情况的处理。
-
86. 分隔链表 - 力扣(LeetCode)
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* partition(ListNode* head, int x) { ListNode* head1=new ListNode; ListNode* res=head1; ListNode* head2=new ListNode; ListNode* res2=head2; ListNode* x_node=new ListNode; x_node->val=x; while(head){ if(head->val<x){ ListNode* temp=new ListNode; temp->val=head->val; head1->next=temp; head1=head1->next; } else{ ListNode* temp=new ListNode; temp->val=head->val; head2->next=temp; head2=head2->next; } head=head->next; } head1->next=res2->next; return res->next; } };
-
23. 合并 K 个升序链表 - 力扣(LeetCode)
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ bool cmp(ListNode* p1,ListNode* p2){ if(p1->val>p2->val){ return true; } else{ return false; } } class Solution { public: /*bool cmp(ListNode* p1,ListNode* p2){ if(p1->val>p2->val){ return true; } else{ return false; } }*/ ListNode* mergeKLists(vector<ListNode*>& lists) { ListNode* head=new ListNode;//虚头节点 ListNode* res=head; /*创建小根堆*/ priority_queue<ListNode*,vector<ListNode*>,decltype(&cmp)> pq(cmp); /*将ListNode放入小根堆中*/ int len=lists.size(); for(int i=0;i<len;i++){ if(lists[i]!=nullptr){ pq.push(lists[i]); } } /*开始循环*/ while(!pq.empty()){ ListNode* temp=pq.top(); pq.pop(); ListNode* node=new ListNode; node->val=temp->val; head->next=node; head=head->next; if(temp->next){ pq.push(temp->next); } } return res->next; } };
用到 优先级队列(二叉堆),优先队列
pq
中的元素个数最多是k
,所以一次poll
或者add
方法的时间复杂度是O(logk)
;所有的链表节点都会被加入和弹出pq
,所以算法整体的时间复杂度是O(Nlogk)
,其中k
是链表的条数,N
是这些链表的节点总数。
参考:
双指针技巧秒杀七道链表题目 | labuladong 的算法笔记c++优先队列(priority_queue)用法详解-CSDN博客c++优先队列priority_queue(自定义比较函数)_c++ priority_queue自定义比较函数-CSDN博客
明天继续~