深圳网站建设知了网络,360收录,wordpress实用,微信小程序定位权限怎么打开链表解题技巧
额外的数据结构#xff08;哈希表#xff09;#xff1b;快慢指针#xff1b;虚拟头节点#xff1b;
链表划分
将单向链表值划分为左边小、中间相等、右边大的形式。中间值为pivot划分值。
要求#xff1a;调整之后节点的相对次序不变#xff0c;时间复…链表解题技巧
额外的数据结构哈希表快慢指针虚拟头节点
链表划分
将单向链表值划分为左边小、中间相等、右边大的形式。中间值为pivot划分值。
要求调整之后节点的相对次序不变时间复杂度不高于O(N)空间复杂度不高于O(1)。
方法1数组 快排
整体思路就是遍历一遍链表把节点存入数组对数组快排然后再遍历数组生成将节点重新连接。
该方法时间复杂度为O(N*logN)空间复杂度为O(N)且会改变相对次序。
但最容易想到和实现。
ListNode* LinkedList::partitionWithPivotAndArray(ListNode *head, int pivot) {if (head nullptr || head-next nullptr) return head;// push into arrayListNode *cur head;std::vectorListNode* arr;while (cur ! nullptr) {arr.push_back(cur);cur cur-next;}// partitionint less -1;int more (int)arr.size();for (int i 0; i more; ) {if (arr[i]-val pivot) {swap(arr[less], arr[i]);} else if (arr[i]-val pivot) {swap(arr[--more], arr[i]);} else {i;}}// rejointint i 1;for (; i (int)arr.size(); i) {arr[i - 1]-next arr[i];}arr[i-1]-next nullptr;return arr[0];
}void LinkedList::swap(ListNode *a, ListNode *b) {ListNode tmp *a;*a *b;*b tmp;
}方法2多个指针
主要是使用6个指针记录3个部分的头、尾位置。
在判定完一个节点属于3个部分的哪个部分后
如果是当前这部分的第一个节点将该部分头部head和tail的位置均赋值为该节点如果不是第一个节点将该部分尾部tail的next指向当前节点tail在移动到该节点
三部分连接
第1部分存在 第2部分存在1尾部连接2头部第2部分不存在1尾部连接3头部 不论第一部分存在与否 第2部分存在2尾部连接3头部
判断头节点
返回less、pivot和more中不为空且在前面的指针即less不为空返回less否则pivot不为空返回pivot否则才返回more。
ListNode* LinkedList::partitionWithPivot(ListNode *head, int pivot) {if (head nullptr || head-next nullptr) return head;ListNode *less_head, *less_tail, *pivot_head, *pivot_tail, *more_head, *more_tail;less_head less_tail pivot_head pivot_tail more_head more_tail nullptr;// partitionListNode *cur head;while (cur) {if (cur-val pivot) {if (less_head nullptr) {less_head less_tail cur;} else {less_tail-next cur;less_tail cur;}} else if (cur-val pivot) {if (pivot_head nullptr) {pivot_head pivot_tail cur;}else {pivot_tail-next cur;pivot_tail cur;}} else {if (more_head nullptr) {more_head more_tail cur;}else {more_tail-next cur;more_tail cur;}}cur cur-next;}// jointif (less_head ! nullptr) {less_tail-next pivot_head ! nullptr ? pivot_head : more_head;}if (pivot_head ! nullptr) {pivot_tail-next more_head;}// final headhead less_head ? less_head : (pivot_head ? pivot_head : more_head);return head;
}Notes
注意处理小于部分、等于部分、大于部分有缺失的情况。
