网站申请专利,网站平台建设需求的意见,网站维护,集客crm目录
7.6合并两个有序链表#xff08;简单#xff09;
7.7两数相加#xff08;中等#xff09;
7.8删除链表的倒数第N个节点#xff08;中等#xff09;
7.9两两交换链表中的节点#xff08;中等#xff09;
7.10k个一组翻转链表#xff08;困难#xff09; 7.6…
目录
7.6合并两个有序链表简单
7.7两数相加中等
7.8删除链表的倒数第N个节点中等
7.9两两交换链表中的节点中等
7.10k个一组翻转链表困难 7.6合并两个有序链表简单
题目描述leetcode链接 21.合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1 输入l1 [1,2,4], l2 [1,3,4]
输出[1,1,2,3,4,4]示例 2 输入l1 [], l2 []
输出[]示例 3 输入l1 [], l2 [0]
输出[0] 思路
1.当list1为空链表直接返回list2当list2为空链表直接返回list1
2.当list1、list2均为非空链表比较list1 - val和list2 - val的大小
如果list1 - val list2 - val则list2 - next mergeTwoLists(list1, list2 - next);
否则list1 - next mergeTwoLists(list1 - next, list2)
举例说明 代码
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if (!list1) return list2;else if (!list2) return list1;else if (list1 - val list2 - val) {list2 - next mergeTwoLists(list1, list2 - next);return list2;}else {list1 - next mergeTwoLists(list1 - next, list2);return list1;}}
};
7.7两数相加中等
题目描述leetcode链接 2.两数相加 给你两个 非空 的链表表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的并且每个节点只能存储 一位 数字。 请你将两个数相加并以相同形式返回一个表示和的链表。 你可以假设除了数字 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.add用于存储进位新建哑结点ListNode* dummy new ListNode(0)用于存储相加后的结果
ListNode* cur dummy
2.只要l1 || l2 || add满足条件
int n1 l1 ? l1 - val : 0;如果l1不是nullptrn1l1 - val否则n10 int n2 l2 ? l2 - val : 0;如果l2不是nullptrn2l2 - val否则n20 int sum n1 n2 add;
sum%10存储结果
add sum/10更新进位结果
3.移动至链表的下一节点重复第2步
cur cur - next; if (l1) l1 l1 - next; if (l2) l2 l2 - next;
4.最后返回dummy - next
举例说明
见上图
代码
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {int add 0;ListNode* dummy new ListNode(0);ListNode* cur dummy;while (l1 || l2 || add) {int n1 l1 ? l1 - val : 0;int n2 l2 ? l2 - val : 0;int sum n1 n2 add;cur - next new ListNode(sum % 10);cur cur - next;add sum / 10;if (l1) l1 l1 - next;if (l2) l2 l2 - next;}ListNode* ans dummy - next;delete dummy;return ans;}
};
7.8删除链表的倒数第N个节点中等
题目描述leetcode链接 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] 思路 1.新建哑结点ListNode* dummy指向链表的头节点
2.利用快慢指针fast和slow均从dummy开始首先令fast向前走N步
3. fast和slow同步向前移动当fast到达链表末端时slow到达待删除节点的上一个节点
4.令slow - next slow - next - next返回dummy - next
举例说明
见上图
代码
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy new ListNode(0);dummy - next head;ListNode* fast dummy;ListNode* slow dummy;while (n--) {if (fast - next) fast fast - next;else return nullptr;}while (fast - next) {fast fast - next;slow slow - next;}slow - next slow - next - next;return dummy - next;}
};
7.9两两交换链表中的节点中等
题目描述leetcode链接 24. 两两交换链表中的节点 给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。 示例 1 输入head [1,2,3,4]
输出[2,1,4,3]示例 2 输入head []
输出[]示例 3 输入head [1]
输出[1] 思路 举例说明
见上图
代码
class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* dummy new ListNode(0);dummy - next head;ListNode* cur dummy;while (cur - next cur - next - next) {ListNode* node1 cur - next;ListNode* node2 cur - next - next;cur - next node2;node1 - next node2 - next;node2 - next node1;cur node1;}return dummy - next;}
};
7.10k个一组翻转链表困难
题目描述leetcode链接 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] 思路
1.遍历链表统计节点个数为n
2.每k个节点翻转一次链表
3.对已翻转的k个节点与前后节点之间的关系进行更新
举例说明 每k个节点翻转一次参考7.2反转链表
已翻转的k个节点与前后节点的关系更新参考7.9两两交换链表中的节点
代码
class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {int n 0;ListNode* dummy new ListNode(0);dummy - next head;ListNode* count head;while (count) {n;count count - next;} ListNode* pre nullptr;ListNode* cur head;ListNode* p0 dummy;for (; n k; n - k) {for (int i 0; i k; i) {ListNode* temp cur - next;cur - next pre;pre cur;cur temp;}ListNode* temp2 p0 - next;p0 - next - next cur;p0 - next pre;p0 temp2;}return dummy - next;}
};
