LeetCode 热题100（七）【链表】（2）

目录

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;}
};