厦门 网站建设 闽icp手机注册网站
目录
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不是nullptr，n1=l1 -> val，否则n1=0）
int n2 = l2 ? l2 -> val : 0;（如果l2不是nullptr，n2=l2 -> val，否则n2=0）
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;}
};