[C/C++] List相关操作

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(vector<ListNode*>& lists) {auto cmp = [](const ListNode *lhs, const ListNode *rhs) {return lhs->val > rhs->val;};// 通过优先级队列进行排序，并将取出的后续节点继续插入priority_queue<ListNode *, vector<ListNode *>, 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;
}