宠物网站设计首页模板德国 网站后缀

当前位置： 首页 > news >正文

宠物网站设计首页模板,德国 网站后缀,株洲网站建设方案咨询,邵阳网站seo简单

1. 合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1#xff1a; 输入#xff1a;l1 [1,2,4], l2 [1,3,4] 输出#xff1a;[1,1,2,3,4,4]示例 2#xff1a; 输入#xff1a;l1 [], l2…简单
2. 合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1 输入l1 [1,2,4], l2 [1,3,4] 输出[1,1,2,3,4,4]示例 2 输入l1 [], l2 [] 输出[]示例 3 输入l1 [], l2 [0] 输出[0]提示 两个链表的节点数目范围是 [0, 50]-100 Node.val 100l1 和 l2 均按 非递减顺序 排列 递归问题可以化为重复子问题既不断合并两个链表所以可以采用递归 ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if (list1 nullptr)return list2;if (list2 nullptr)return list1;if (list1-val list2-val) {list1-next mergeTwoLists(list1-next, list2);return list1;} else {list2-next mergeTwoLists(list1, list2-next);return list2; } }迭代 ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* newhead new ListNode;ListNode* cur newhead;while (list1 list2) {if (list1-val list2-val) {cur-next list1;list1 list1-next;} else {cur-next list2;list2 list2-next;}cur cur-next;}cur-next (list1 ? list1 : list2);ListNode* ans newhead-next;delete newhead;return ans; }141. 环形链表 给你一个链表的头节点 head 判断链表中是否有环。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 如果链表中存在环 则返回 true 。 否则返回 false 。 示例 1 输入head [3,2,0,-4], pos 1 输出true 解释链表中有一个环其尾部连接到第二个节点。示例 2 输入head [1,2], pos 0 输出true 解释链表中有一个环其尾部连接到第一个节点。示例 3 输入head [1], pos -1 输出false 解释链表中没有环。提示 链表中节点的数目范围是 [0, 10^4]-10^5 Node.val 10^5pos 为 -1 或者链表中的一个 有效索引 。 进阶你能用 O(1)即常量内存解决此问题吗 哈希 如果链表中存在环链表中有重复的地址出现如果没有环则退出循环。 bool hasCycle(ListNode head) {unordered_setListNode hash;while (head) {if (hash.count(head))return true;hash.insert(head);head head-next;}return false; }快慢指针 如果链表中存在环那么 fast 指针会先进入环然后在环中不断循环。由于 fast 指针移动速度比 slow 指针快最终 fast 指针会追上 slow 指针即 slow 指针和 fast 指针会相遇。如果链表中不存在环那么 fast 指针会先到达链表的末尾即 fast-next 或 fast-next-next 为 nullptr此时循环结束说明链表中不存在环。 bool hasCycle(ListNode head) {if (head nullptr)return false;ListNode slow head, *fast head;while (fast-next fast-next-next) {slow slow-next;fast fast-next-next;if (slow fast)return true;}return false; }160. 相交链表 给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。 图示两个链表在节点 c1 开始相交**** 题目数据 保证 整个链式结构中不存在环。 注意函数返回结果后链表必须 保持其原始结构 。 自定义评测 评测系统 的输入如下你设计的程序 不适用 此输入 intersectVal - 相交的起始节点的值。如果不存在相交节点这一值为 0listA - 第一个链表listB - 第二个链表skipA - 在 listA 中从头节点开始跳到交叉节点的节点数skipB - 在 listB 中从头节点开始跳到交叉节点的节点数 评测系统将根据这些输入创建链式数据结构并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点那么你的解决方案将被 视作正确答案 。 示例 1 输入intersectVal 8, listA [4,1,8,4,5], listB [5,6,1,8,4,5], skipA 2, skipB 3 输出Intersected at 8 解释相交节点的值为 8 注意如果两个链表相交则不能为 0。 从各自的表头开始算起链表 A 为 [4,1,8,4,5]链表 B 为 [5,6,1,8,4,5]。 在 A 中相交节点前有 2 个节点在 B 中相交节点前有 3 个节点。 — 请注意相交节点的值不为 1因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说它们在内存中指向两个不同的位置而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点B 中第四个节点) 在内存中指向相同的位置。示例 2 输入intersectVal 2, listA [1,9,1,2,4], listB [3,2,4], skipA 3, skipB 1 输出Intersected at 2 解释相交节点的值为 2 注意如果两个链表相交则不能为 0。 从各自的表头开始算起链表 A 为 [1,9,1,2,4]链表 B 为 [3,2,4]。 在 A 中相交节点前有 3 个节点在 B 中相交节点前有 1 个节点。示例 3 输入intersectVal 0, listA [2,6,4], listB [1,5], skipA 3, skipB 2 输出No intersection 解释从各自的表头开始算起链表 A 为 [2,6,4]链表 B 为 [1,5]。 由于这两个链表不相交所以 intersectVal 必须为 0而 skipA 和 skipB 可以是任意值。 这两个链表不相交因此返回 null 。提示 listA 中节点数目为 mlistB 中节点数目为 n1 m, n 3 * 10^41 Node.val 10^50 skipA m0 skipB n如果 listA 和 listB 没有交点intersectVal 为 0如果 listA 和 listB 有交点intersectVal listA[skipA] listB[skipB] 进阶你能否设计一个时间复杂度 O(m n) 、仅用 O(1) 内存的解决方案 哈希 找到第一个重复出现的地址。 ListNode *getIntersectionNode(ListNode *headA, ListNode headB) {unordered_setListNode hash;while (headA) {hash.insert(headA);headA headA-next;}while (headB) {if (hash.count(headB))return headB;headB headB-next;}return nullptr; }双指针 指针 curA 先遍历链表 A 的不相交部分长度为 a - c然后遍历相交部分当遍历到相交部分末尾时如果还没有和 curB 相遇它会跳到链表 B 的头部继续遍历。此时它总共遍历的节点数为 a - c b - c。 指针 curB 先遍历链表 B 的不相交部分长度为 b - c然后遍历相交部分当遍历到相交部分末尾时如果还没有和 curA 相遇它会跳到链表 A 的头部继续遍历。此时它总共遍历的节点数为 b - c a - c。 如果没有相交节点c 0curA和curB会在都为空时相遇并退出循环。
   图片原题解 ListNode *getIntersectionNode(ListNode *headA, ListNode headB) {if (headA nullptr || headB nullptr)return nullptr;ListNode curA headA, * curB headB;while (curA ! curB) {curA curA nullptr ? headB : curA-next;curB curB nullptr ? headA : curB-next;}return curA; }206. 反转链表 给你单链表的头节点 head 请你反转链表并返回反转后的链表。 示例 1 输入head [1,2,3,4,5] 输出[5,4,3,2,1]示例 2 输入head [1,2] 输出[2,1]示例 3 输入head [] 输出[]提示 链表中节点的数目范围是 [0, 5000]-5000 Node.val 5000 进阶链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题 迭代 ListNode* reverseList(ListNode* head) {ListNode* cur head;ListNode* prev nullptr;while (cur) {ListNode* next cur-next;cur-next prev;prev cur;cur next;}return prev; }递归 ListNode* reverseList(ListNode* head) {if (head nullptr || head-next nullptr)return head;ListNode* new_head reverseList(head-next);head-next-next head;head-next nullptr;return new_head; }234. 回文链表 给你一个单链表的头节点 head 请你判断该链表是否为回文链表如果是返回 true 否则返回 false。 回文 序列是向前和向后读都相同的序列 示例 1 输入head [1,2,2,1] 输出true示例 2 输入head [1,2] 输出false提示 链表中节点数目在范围[1, 10^5] 内0 Node.val 9 进阶你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题 数组模拟 bool isPalindrome(ListNode* head) {vectorint nums;while (head) {nums.push_back(head-val);head head-next;}int left 0, right nums.size() - 1;while (left right) {if (nums[left] ! nums[right])return false;left;right–;}return true; }找到链表的中间节点再逆置后比对 // 876. 链表的中间结点 ListNode* middleNode(ListNode* head) {ListNode* slow head, * fast head;while (fast fast-next) {slow slow-next;fast fast-next-next;}return slow; }// 206. 反转链表 ListNode* reverseList(ListNode* head) {ListNode* cur head;ListNode* prev nullptr;while (cur) {ListNode* next cur-next;cur-next prev;prev cur;cur next;}return prev; }bool isPalindrome(ListNode* head) {ListNode* mid middleNode(head);mid reverseList(mid);while (mid) {if (head-val ! mid-val)return false;head head-next;mid mid-next;}return true; }876. 链表的中间结点 给你单链表的头结点 head 请你找出并返回链表的中间结点。 如果有两个中间结点则返回第二个中间结点。 示例 1 输入head [1,2,3,4,5] 输出[3,4,5] 解释链表只有一个中间结点值为 3 。示例 2 输入head [1,2,3,4,5,6] 输出[4,5,6] 解释该链表有两个中间结点值分别为 3 和 4 返回第二个结点。提示 链表的结点数范围是 [1, 100]1 Node.val 100 快慢指针 ListNode* middleNode(ListNode* head) {ListNode* slow head, * fast head;while (fast fast-next) {slow slow-next;fast fast-next-next;}return slow; }中等
3. 两数相加 给你两个 非空 的链表表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的并且每个节点只能存储 一位 数字。 请你将两个数相加并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外这两个数都不会以 0 开头。 示例 1 输入l1 [2,4,3], l2 [5,6,4] 输出[7,0,8] 解释342 465 807.示例 2 输入l1 [0], l2 [0] 输出[0]示例 3 输入l1 [9,9,9,9,9,9,9], l2 [9,9,9,9] 输出[8,9,9,9,0,0,0,1]提示 每个链表中的节点数在范围 [1, 100] 内0 Node.val 9题目数据保证列表表示的数字不含前导零 根据题意将链表中的两数相加即可通过创建newhead可以避免新链表判断是否有头节点。 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {int t 0, sum 0;ListNode* newhead new ListNode;ListNode* cur newhead;ListNode* cur1 l1,* cur2 l2;while (cur1 cur2) {sum cur1-val cur2-val t;cur-next new ListNode(sum % 10); cur cur-next;t sum / 10;cur1 cur1-next;cur2 cur2-next;}while (cur1) {sum cur1-val t;cur-next new ListNode(sum % 10); cur cur-next;t sum / 10;cur1 cur1-next;}while (cur2) {sum cur2-val t;cur-next new ListNode(sum % 10); cur cur-next; t sum / 10;cur2 cur2-next;}if (t)cur-next new ListNode(t);return newhead-next; }对上面代码进行优化。 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {int sum 0;ListNode* newhead new ListNode;ListNode* cur newhead;ListNode* cur1 l1,* cur2 l2;while (cur1 || cur2 || sum) {if (cur1) {sum cur1-val;cur1 cur1-next;}if (cur2) {sum cur2-val;cur2 cur2-next;}cur-next new ListNode(sum % 10); cur cur-next;sum / 10;}return newhead-next; }19. 删除链表的倒数第 N 个结点 给你一个链表删除链表的倒数第 n 个结点并且返回链表的头结点。 示例 1 输入head [1,2,3,4,5], n 2 输出[1,2,3,5]示例 2 输入head [1], n 1 输出[]示例 3 输入head [1,2], n 1 输出[1]提示 链表中结点的数目为 sz1 sz 300 Node.val 1001 n sz 进阶你能尝试使用一趟扫描实现吗 计算链表长度转化为删除链表第(len - n)个节点。 ListNode* removeNthFromEnd(ListNode* head, int n) {int len 0;ListNode* cur head;while (cur) {cur cur-next;len;}int k len - n;cur head;ListNode* prev nullptr;while (k–) {prev cur;cur cur-next;}if (prev nullptr)return head-next;prev-next cur-next;return head; }快慢指针fast指针快slow指针(n 1)个当fast为空时slow刚好为要删除的节点前一个 ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* new_head new ListNode(0, head);ListNode* fast head;ListNode* slow new_head;while (n–) {fast fast-next;}while (fast) {slow slow-next;fast fast-next;}slow-next slow-next-next;ListNode* ans new_head-next;delete new_head;return ans; }24. 两两交换链表中的节点 给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。 示例 1 输入head [1,2,3,4] 输出[2,1,4,3]示例 2 输入head [] 输出[]示例 3 输入head [1] 输出[1]提示 链表中节点的数目在范围 [0, 100] 内0 Node.val 100 递归 ListNode* swapPairs(ListNode* head) {if (head nullptr || head-next nullptr)return head;ListNode* newhead head-next;// 先交换当前两个节点后面的节点再交换当前两个节点head-next swapPairs(newhead-next);newhead-next head;return newhead; }迭代将需要交换的左右节点以及左节点的前节点和后节点定义便于交换操作。 ListNode* swapPairs(ListNode* head) {if (head nullptr || head-next nullptr)return head;ListNode* newhead new ListNode(0, head);ListNode* prev newhead;ListNode* left head;ListNode* right head-next;ListNode* next right-next;while (left right) {left-next next;right-next left;prev-next right;prev left;left prev-next;if (left)right left-next;if (right)next right-next;}return newhead-next; }138. 随机链表的复制 给你一个长度为 n 的链表每个节点包含一个额外增加的随机指针 random 该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。 例如如果原链表中有 X 和 Y 两个节点其中 X.random – Y 。那么在复制链表中对应的两个节点 x 和 y 同样有 x.random – y 。 返回复制链表的头节点。 用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示 val一个表示 Node.val 的整数。random_index随机指针指向的节点索引范围从 0 到 n-1如果不指向任何节点则为 null 。 你的代码 只 接受原链表的头节点 head 作为传入参数。 示例 1 输入head [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出[[7,null],[13,0],[11,4],[10,2],[1,0]]示例 2 输入head [[1,1],[2,1]] 输出[[1,1],[2,1]]示例 3 输入head [[3,null],[3,0],[3,null]] 输出[[3,null],[3,0],[3,null]]提示 0 n 1000-10^4 Node.val 10^4Node.random 为 null 或指向链表中的节点。 递归回溯 // 旧节点对应新节点 unordered_mapNode, Node cache_node;Node* copyRandomList(Node* head) {if (head nullptr) return nullptr;if (!cache_node.count(head)) { // 未复制这个节点Node* new_node new Node(head-val);cache_node[head] new_node;new_node-next copyRandomList(head-next);new_node-random copyRandomList(head-random);}return cache_node[head]; }迭代 节点拆分对于链表 A→B→C我们可以将其拆分为 A→A ′ →B→B ′ →C→C ′ 。对于任意一个原节点 S其拷贝节点 S ′即为其后继节点。 Node* copyRandomList(Node* head) {if (head nullptr)return nullptr;// 插入新节点到原链表中for (Node* cur head; cur ! nullptr; cur cur-next-next) {Node* new_node new Node(cur-val);new_node-next cur-next;cur-next new_node;}// 复制随机指针for (Node* cur head; cur ! nullptr; cur cur-next-next) {Node* new_node cur-next;new_node-random (cur-random ? cur-random-next : nullptr);}// 拆分链表Node* new_head head-next;for (Node* cur head; cur ! nullptr; cur cur-next) {Node* new_node cur-next;cur-next cur-next-next;new_node-next (new_node-next ? new_node-next-next : nullptr);}return new_head; }142. 环形链表 II 给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。 不允许修改 链表。 示例 1 输入head [3,2,0,-4], pos 1 输出返回索引为 1 的链表节点 解释链表中有一个环其尾部连接到第二个节点。示例 2 输入head [1,2], pos 0 输出返回索引为 0 的链表节点 解释链表中有一个环其尾部连接到第一个节点。示例 3 输入head [1], pos -1 输出返回 null 解释链表中没有环。提示 链表中节点的数目范围在范围 [0, 10^4] 内-105 Node.val 10^5pos 的值为 -1 或者链表中的一个有效索引 进阶你是否可以使用 O(1) 空间解决此题 哈希 如果链表中存在环链表中第一次重复出现的地址就是入环的第一个节点如果没有环则退出循环。 ListNode *detectCycle(ListNode head) {unordered_setListNode hash;while (head) {if (hash.count(head))return head;hash.insert(head);head head-next;}return nullptr; }快慢指针 设链表头节点到环入口节点的距离为 a环入口节点到快慢指针相遇节点的距离为 b相遇节点再到环入口节点的距离为 c。 当快慢指针相遇时slow 指针走过的距离为 a bfast 指针走过的距离为 a b k * (b c)k 为 fast 指针在环内绕的圈数k 1。由于 fast 指针速度是 slow 指针的两倍所以有 2 * (a b) a b k * (b c)化简可得 a (k - 1) * (b c) c既a等于c加上k - 1圈的长度。这意味着从链表头节点和快慢指针相遇节点同时出发以相同速度前进它们会在环的入口节点相遇。 ListNode *detectCycle(ListNode head) {if (head nullptr)return nullptr;ListNode slow head, *fast head;while (fast-next fast-next-next) {slow slow-next;fast fast-next-next;if (slow fast) {while (head ! slow) {head head-next;slow slow-next;}return slow;}}return nullptr; }143. 重排链表 给定一个单链表 L 的头节点 head 单链表 L 表示为 L0 → L1 → … → Ln - 1 → Ln请将其重新排列后变为 L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …不能只是单纯的改变节点内部的值而是需要实际的进行节点交换。 示例 1 输入head [1,2,3,4] 输出[1,4,2,3]示例 2 输入head [1,2,3,4,5] 输出[1,5,2,4,3]提示 链表的长度范围为 [1, 5 * 104]1 node.val 1000 876. 链表的中间结点 206. 反转链表 合并链表 ListNode* reverseList(ListNode* head) {ListNode* prev nullptr;ListNode* cur head;while (cur) {ListNode* next cur-next;cur-next prev;prev cur;cur next;}return prev; }ListNode* middleNode(ListNode* head) {ListNode* slow head;ListNode* fast head;while (fast fast-next) {slow slow-next;fast fast-next-next;}return slow; }void reorderList(ListNode* head) {ListNode* mid middleNode(head);ListNode* l1 head;ListNode* l2 mid-next;mid-next nullptr;l2 reverseList(l2);// 合并while (l1 l2) {ListNode* l1_tmp l1-next;ListNode* l2_tmp l2-next;l1-next l2;l1 l1_tmp;l2-next l1;l2 l2tmp;} }146. LRU 缓存 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类 LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中则返回关键字的值否则返回 -1 。void put(int key, int value) 如果关键字 key 已经存在则变更其数据值 value 如果不存在则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity 则应该 逐出 最久未使用的关键字。 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。 示例 输入 [LRUCache, put, put, get, put, get, put, get, get, get] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 输出 [null, null, null, 1, null, -1, null, -1, 3, 4]解释 LRUCache lRUCache new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {11} lRUCache.put(2, 2); // 缓存是 {11, 22} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废缓存是 {11, 33} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废缓存是 {44, 33} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4提示 1 capacity 30000 key 100000 value 105最多调用 2 * 105 次 get 和 put 哈希表 双向链表 get和put方法 要求O(1) 的平均时间复杂度所以想到用哈希表用带伪头节点和伪尾节点双向链表来维护缓存便于不断更新头节点删除节点 get 方法 尝试从哈希表中查找键为 key 的节点。如果节点不存在返回 -1。如果节点存在将该节点移动到双向链表的头部表示最近使用然后返回节点的值。 put 方法 如果键key不存在于缓存中 创建一个新的节点并将其插入到双向链表的头部。将该节点的信息存入哈希表。如果缓存大小超过容量删除双向链表的尾节点即最近最少使用的节点并从哈希表中移除对应的记录。 如果键key已经存在于缓存中 更新该节点的值。将该节点移动到双向链表的头部
   struct DLinkNode {int key, value;DLinkNode* next;DLinkNode* prev;DLinkNode() : key(0), value(0), next(nullptr), prev(nullptr) {}DLinkNode(int key, int value) : key(key), value(value), next(nullptr), prev(nullptr) {} };class LRUCache { private:DLinkNode* head; // 伪头部DLinkNode* tail_; // 伪尾部unorderedmapint, DLinkNode* cache;int size;int capacity; public:LRUCache(int capacity) : size(0), capacity(capacity) {head_ new DLinkNode();tail_ new DLinkNode();head-next tail;tail-prev head;}int get(int key) {if (!cache.count(key))return -1;DLinkNode* node cache[key];moveToHead(node);return node-value;}void put(int key, int value) {if (!cache.count(key)) { // key不存在创建新节点DLinkNode* node new DLinkNode(key, value);cache[key] node;addToHead(node);size;if (size capacity) { // 超出缓存容量删除尾节点DLinkNode* removed removeTail();cache.erase(removed-key);delete removed;–size;}} else { // key存在更新value移至头部DLinkNode* node cache[key];node-value value;moveToHead(node);}}private:void removeNode(DLinkNode* node) {node-prev-next node-next;node-next-prev node-prev;}void addToHead(DLinkNode* node) {DLinkNode* head head-next;head-prev node;node-next head;head-next node;node-prev head;}void moveToHead(DLinkNode* node) {removeNode(node);addToHead(node);}DLinkNode* removeTail() {DLinkNode* node tail-prev;removeNode(node);return node;} };
4. 对链表进行插入排序 给定单个链表的头 head 使用 插入排序 对链表进行排序并返回 排序后链表的头 。 插入排序 算法的步骤: 插入排序是迭代的每次只移动一个元素直到所有元素可以形成一个有序的输出列表。每次迭代中插入排序只从输入数据中移除一个待排序的元素找到它在序列中适当的位置并将其插入。重复直到所有输入数据插入完为止。 下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时从输入数据中删除一个元素(红色)并就地插入已排序的列表中。 对链表进行插入排序。 示例 1 输入: head [4,2,1,3] 输出: [1,2,3,4]示例 2 输入: head [-1,5,3,4,0] 输出: [-1,0,3,4,5]提示 列表中的节点数在 [1, 5000]范围内-5000 Node.val 5000 ListNode* insertionSortList(ListNode* head) {ListNode* new_head new ListNode(0, head);ListNode* cur head-next;ListNode* prev head;while (cur) {if (cur-val prev-val) {ListNode* pos new_head;while (pos-next-val cur-val)pos pos-next;prev-next cur-next;cur-next pos-next;pos-next cur;}prev cur;cur cur-next;}ListNode* ans new_head-next;delete new_head;return ans; }148. 排序链表 给你链表的头结点 head 请将其按 升序 排列并返回 排序后的链表 。 示例 1 输入head [4,2,1,3] 输出[1,2,3,4]示例 2 输入head [-1,5,3,4,0] 输出[-1,0,3,4,5]示例 3 输入head [] 输出[]提示 链表中节点的数目在范围 [0, 5 * 104] 内-105 Node.val 105 进阶你可以在 O(n log n) 时间复杂度和常数级空间复杂度下对链表进行排序吗 归并排序通过快慢指针找到中间节点递归地对链表进行分治排序。 ListNode* merge(ListNode* list1, ListNode* list2) {ListNode* new_head new ListNode;ListNode* cur new_head;while (list1 list2) {if (list1-val list2-val) {cur-next list1;list1 list1-next;} else {cur-next list2;list2 list2-next;}cur cur-next;}cur-next (list1 ? list1 : list2);ListNode* head new_head-next;delete new_head;return head; }ListNode* sortList(ListNode* head, ListNode* tail) {if (head nullptr)return head;if (head-next tail) {head-next nullptr;return head;}ListNode* slow head, * fast head;while (fast ! tail fast-next ! tail) {slow slow-next;fast fast-next-next;}ListNode* mid slow;return merge(sortList(head, mid), sortList(mid, tail)); }ListNode* sortList(ListNode* head) {return sortList(head, nullptr); }困难
5. 合并 K 个升序链表 给你一个链表数组每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中返回合并后的链表。 示例 1 输入lists [[1,4,5],[1,3,4],[2,6]] 输出[1,1,2,3,4,4,5,6] 解释链表数组如下 [1-4-5,1-3-4,2-6 ] 将它们合并到一个有序链表中得到。 1-1-2-3-4-4-5-6示例 2 输入lists [] 输出[]示例 3 输入lists [[]] 输出[]提示 k lists.length0 k 10^40 lists[i].length 500-10^4 lists[i][j] 10^4lists[i] 按 升序 排列lists[i].length 的总和不超过 10^4 暴力解法 根据21. 合并两个有序链表这题不断合并所有链表。 ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* newhead new ListNode;ListNode* cur newhead;while (list1 list2) {if (list1-val list2-val) {cur-next list1;list1 list1-next;} else {cur-next list2;list2 list2-next;}cur cur-next;}cur-next (list1 ? list1 : list2);return newhead-next; }ListNode* mergeKLists(vectorListNode* lists) {ListNode* ans nullptr;for (ListNode* list : lists)ans mergeTwoLists(ans, list);return ans; }分治合并 和归并排序的思想一样不断将链表的头节点分成两部分先分别对这两部分合并再将这两部分合并。 ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* new_head new ListNode;ListNode* cur new_head;while (list1 list2) {if (list1-val list2-val) {cur-next list1;list1 list1-next;} else {cur-next list2;list2 list2-next;}cur cur-next;}cur-next (list1 ? list1 : list2);return new_head-next; }ListNode* merge(vectorListNode* lists, int left, int right) {if (left right) return nullptr;if (left right) return lists[left];int mid left (right - left) / 2;return mergeTwoLists(merge(lists, left, mid), merge(lists, mid 1, right)); }ListNode* mergeKLists(vectorListNode* lists) {int n lists.size();return merge(lists, 0, n - 1); }优先级队列 借助优先级队列找到最小的未被合并的头节点不断合并。 struct cmp {bool operator()(ListNode* list1, ListNode* list2) {return list1-val list2-val;} };ListNode* mergeKLists(vectorListNode* lists) {// 建立小根堆priority_queueListNode, vectorListNode, cmp heap;// 所有头节点入队for (ListNode* list : lists)if (list)heap.push(list);// 合并k个有序链表ListNode* new_head new ListNode;ListNode* cur new_head;while (!heap.empty()) {ListNode* t heap.top();heap.pop();if (t-next)heap.push(t-next);cur-next t;cur cur-next;}return new_head-next; }25. K 个一组翻转链表 给你链表的头节点 head 每 k 个节点一组进行翻转请你返回修改后的链表。 k 是一个正整数它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍那么请将最后剩余的节点保持原有顺序。 你不能只是单纯的改变节点内部的值而是需要实际进行节点交换。 示例 1 输入head [1,2,3,4,5], k 2 输出[2,1,4,3,5]示例 2 输入head [1,2,3,4,5], k 3 输出[3,2,1,4,5]提示 链表中的节点数目为 n1 k n 50000 Node.val 1000 进阶你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗 模拟 每k个节点进行一次206. 反转链表并记录新的头和尾用于整个链表的连接。 pairListNode, ListNode reverseList(ListNode* head, ListNode* tail) {ListNode* prev tail-next;ListNode* cur head;while (prev ! tail) {ListNode* next cur-next;cur-next prev;prev cur;cur next;}return {tail, head}; }ListNode* reverseKGroup(ListNode* head, int k) {ListNode* new_head new ListNode(0, head);ListNode* cur new_head;while (cur) {ListNode* tail cur;for (int i 0; i k; i) {tail tail-next;if (tail nullptr)return new_head-next;}auto p reverseList(cur-next, tail);head p.first;tail p.second;cur-next head;cur tail;}return new_head-next; }k 是一个正整数它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍那么请将最后剩余的节点保持原有顺序。 你不能只是单纯的改变节点内部的值而是需要实际进行节点交换。 示例 1 输入head [1,2,3,4,5], k 2 输出[2,1,4,3,5]示例 2 输入head [1,2,3,4,5], k 3 输出[3,2,1,4,5]提示 链表中的节点数目为 n1 k n 50000 Node.val 1000 进阶你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗 模拟 每k个节点进行一次206. 反转链表并记录新的头和尾用于整个链表的连接。 pairListNode, ListNode reverseList(ListNode* head, ListNode* tail) {ListNode* prev tail-next;ListNode* cur head;while (prev ! tail) {ListNode* next cur-next;cur-next prev;prev cur;cur next;}return {tail, head}; }ListNode* reverseKGroup(ListNode* head, int k) {ListNode* new_head new ListNode(0, head);ListNode* cur new_head;while (cur) {ListNode* tail cur;for (int i 0; i k; i) {tail tail-next;if (tail nullptr)return new_head-next;}auto p reverseList(cur-next, tail);head p.first;tail p.second;cur-next head;cur tail;}return new_head-next; }