LeetCode 热题100（七）【链表】（2）
目录
7.6合并两个有序链表（简单）
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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个一组翻转链表（困难）
给你链表的头节点
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;
}
};原文地址：https://blog.csdn.net/jrrz0828/article/details/143369782
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！