网站用哪个软件做,网站开发的私活,开发商城网站建设,网站建设及安全管理文档链表常用技巧和操作总结
常用技巧 画图 引入虚拟头节点 不要吝啬空间#xff0c;大胆定义变量 快慢双指针常用操作 创建一个新节点 尾插 头插
两数相加
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {int carry 0;ListNode* newHead new ListNode, *cur newHea…链表常用技巧和操作总结
常用技巧 画图 引入虚拟头节点 不要吝啬空间大胆定义变量 快慢双指针常用操作 创建一个新节点 尾插 头插
两数相加
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {int carry 0;ListNode* newHead new ListNode, *cur newHead;while (l1 ! nullptr l2 ! nullptr) {int num l1-val l2-val carry;carry num / 10;num num % 10;cur-next new ListNode(num);cur cur-next;l1 l1-next;l2 l2-next;}while (l1 ! nullptr) {int num l1-val carry;carry num / 10;num num % 10;cur-next new ListNode(num);cur cur-next;l1 l1-next;}while (l2 ! nullptr) {int num l2-val carry;carry num / 10;num num % 10;cur-next new ListNode(num);cur cur-next;l2 l2-next;}if (carry ! 0) {cur-next new ListNode(carry);}return newHead-next;
}两两交换链表中的节点
ListNode* swapPairs(ListNode* head) {if (head nullptr || head-next nullptr) return head;ListNode *front head, *back front-next, *newHead new ListNode, *cur newHead;while (true) {cur-next back;ListNode* tmp back-next;back-next front;front-next tmp;cur front;if (tmp ! nullptr tmp-next ! nullptr) {front tmp;back front-next;} else if (tmp ! nullptr tmp-next nullptr) {cur-next tmp;return newHead-next;} else {return newHead-next;}}
}重排链表
ListNode* reverse(ListNode* head) {if (head nullptr || head-next nullptr) return head;ListNode* newHead reverse(head-next);head-next-next head;head-next nullptr;return newHead;
}
void reorderList(ListNode* head) {ListNode *slow head, *fast head;while (fast ! nullptr fast-next ! nullptr) {slow slow-next;fast fast-next-next;}ListNode* cur1 head, *cur2 reverse(slow);ListNode* newHead new ListNode, *cur newHead;while (cur1 ! cur2 cur2 ! nullptr) {cur-next cur1;cur1 cur1-next;cur cur-next;cur-next cur2;cur2 cur2-next;cur cur-next;}
}合并 K 个升序链表
// 解法一
ListNode* mergeKLists(vectorListNode* lists) {// 小根堆priority_queueListNode*, vectorListNode*, Comp pq;for (ListNode* e : lists) {if (e ! nullptr) {pq.push(e);}}ListNode *newHead new ListNode, *cur newHead;while (!pq.empty()) {cur-next pq.top();cur cur-next;pq.pop();if (cur-next ! nullptr) {pq.push(cur-next);}}return newHead-next;
}// 解法二
ListNode* merge_sort(vectorListNode* lists, int start, int end) {if (start end) return nullptr;else if (start end) return lists[start];int mid start (end - start) / 2;ListNode* left merge_sort(lists, start, mid);ListNode* right merge_sort(lists, mid 1, end);if (left nullptr) return right;else if (right nullptr) return left;ListNode *newHead new ListNode, *cur newHead;while (left ! nullptr right ! nullptr) {if (left-val right-val) {cur-next left;left left-next;} else {cur-next right;right right-next;}cur cur-next;}while (left ! nullptr) {cur-next left;left left-next;cur cur-next;}while (right ! nullptr) {cur-next right;right right-next;cur cur-next;}return newHead-next;
}
ListNode* mergeKLists(vectorListNode* lists) {return merge_sort(lists, 0, lists.size() - 1);
}K 个一组翻转链表
ListNode* reverseKGroup(ListNode* head, int k) {int total 0;ListNode* cur head;while (cur ! nullptr) {total;cur cur-next;}ListNode* newHead new ListNode;cur newHead;while (head ! nullptr) {int count k;ListNode* tail head;if (total k) {while (count-- head ! nullptr) {ListNode* tmp head-next;head-next cur-next;cur-next head;head tmp;}total - k;}cur tail;if (total k) {cur-next head;break;}}return newHead-next;
}
