链表
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, 104]内 -105 <= Node.val <= 105pos的值为-1或者链表中的一个有效索引
纯技巧题，相较于 环形链表，多了一个找环起点的要求，也是固定套路
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* fast = head;
ListNode* slow = head;
while(fast != nullptr && fast->next != nullptr){
fast = fast->next->next;
slow = slow->next;
// 相遇即有环，有环找起点
if(fast == slow){
ListNode* n1 = fast;//或 slow，反正此时 fast == slow
ListNode* n2 = head;
while(n1 != n2){
n1 = n1->next;
n2 = n2->next;
}
return n2;
}
}
return nullptr;
}
}
21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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均按 非递减顺序 排列
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0); // 新链表的头结点
ListNode* cur = dummy; // 当前节点
while (l1 != NULL && l2 != NULL) { // 两个链表都不为空时
if (l1->val < l2->val) { // l1的值较小
cur->next = l1; // 将l1连接到新链表中
l1 = l1->next; // l1指针向后移动
} else { // l2的值较小或相等
cur->next = l2; // 将l2连接到新链表中
l2 = l2->next; // l2指针向后移动
}
cur = cur->next; // 新链表的指针向后移动
}
// 如果其中一个链表为空，将另一个非空链表的剩余部分连接到新链表的尾部
if (l1 != NULL) {
cur->next = l1;
}
if (l2 != NULL) {
cur->next = l2;
}
return dummy->next; // 返回新链表的头结点
}
};
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, 100]内 0 <= Node.val <= 9- 题目数据保证列表表示的数字不含前导零
关键在于想到设置 Carry 记录进位
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
//虚拟头节点
ListNode* res = new ListNode(0);
//游标
ListNode* cur = res;
//进位
int carry = 0;
//存在非空就能运算
while(l1 || l2){
//有一个为空时，相当于补0⃣️
int num1 = l1 ? l1->val : 0;
int num2 = l2 ? l2->val : 0;
//不去进位所得和
int sum = num1 + num2 + carry;
//进位
carry = sum / 10;
//去进位所得和
sum %= 10;
//新建用于记录和的节点
cur->next = new ListNode(sum);
cur = cur->next;
//非空继续步进
if(l1) l1 = l1->next;
if(l2) l2 = l2->next;
}
//处理完所有节点后，仍存在进位，则补上最后的进位
if(carry){
cur->next = new ListNode(1);
}
return res->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]
提示：
- 链表中结点的数目为
sz 1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
class Solution {
public:
// 思路：双指针间隔，快指针先步进n，再同步步进
ListNode* removeNthFromEnd(ListNode* head, int n) {
//引入虚拟头节点，保证操作的一致性（即使要删除的是 head，也复用相同操作）
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* fast = dummyHead;
ListNode* slow = dummyHead;
while(n-- && fast!=nullptr){
fast = fast->next;
}
//多走一步，抵消虚拟头节点的影响
//保证 fast 到 nullptr 时，slow->next 刚好为要删除的节点（倒数第 n 个节点）
fast = fast->next;
while(fast != nullptr){
fast = fast->next;
slow = slow->next;
}
//删除指针
slow->next = slow->next->next;
return dummyHead->next;
}
};
24. 两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]
提示：
- 链表中节点的数目在范围
[0, 100]内 0 <= Node.val <= 100
纯技巧题
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* l1 = dummyHead;
ListNode* l2 = dummyHead->next;
while(l2!=nullptr && l2->next!=nullptr){
l1->next = l2->next;
l2->next = l1->next->next;
l1->next->next = l2;
l1 = l2;
l2 = l2->next;
}
return dummyHead->next;
}
};