建立销售型网站,美容网站建设一个多少钱,企业传统网站开发实例,小米软件开发工程师待遇List相关操作
1 链表二分
目标#xff1a; #xff08;1#xff09;对于偶数节点#xff0c;正好对半分#xff1b; #xff08;2#xff09;对于奇数节点#xff0c;前 后 1 #xff08;3#xff09;断开链表#xff0c;方便后期合并
// 使用快慢指针完成中点…List相关操作
1 链表二分
目标 1对于偶数节点正好对半分 2对于奇数节点前 后 1 3断开链表方便后期合并
// 使用快慢指针完成中点拆分
ListNode *SplitList(ListNode *head) {ListNode *slow{head};ListNode *fast{head};while (fast-next ! nullptr fast-next-next ! nullptr) {slow slow-next;fast fast-next-next;}ListNode *mid slow-next;slow-next nullptr;return mid;
}2 链表合并
ListNode *MergeList(ListNode *head1, ListNode *head2) {ListNode dummy{};ListNode *cur dummy;while (head1 ! nullptr head2 ! nullptr) {if (head1-val head2-val) {cur-next head1;head1 head1-next;} else {cur-next head2;head2 head2-next;}cur cur-next;}cur-next (head1 ! nullptr) ? head1 : head2;return dummy.next;
}3 链表排序
ListNode* sortList(ListNode* head) {// 题目进阶要求 nlgn 希尔/归并/快速/堆if (head nullptr || head-next nullptr) {return head;}ListNode *head2 SplitList(head);head sortList(head);head2 sortList(head2);return MergeList(head, head2);
}4 多链表合并
ListNode* mergeKLists(vectorListNode* lists) {auto cmp [](const ListNode *lhs, const ListNode *rhs) {return lhs-val rhs-val;};// 通过优先级队列进行排序并将取出的后续节点继续插入priority_queueListNode *, vectorListNode *, decltype(cmp) pq{};for (auto head : lists) {if (head ! nullptr) {pq.push(head);}}ListNode dummy{};ListNode *cur dummy;while (!pq.empty()) {// 取最小ListNode *node pq.top();pq.pop();if (node-next ! nullptr) {pq.push(node-next);}cur-next node;cur node;}return dummy.next;
}
