不要觉得力扣核心代码模式麻烦，它确实比不上ACM模式舒服，可以自己处理输入输出
只是你对 链表 和 return 的理解不到位
👂 ▶ 屿前世 (163.com)
👂 ▶ see you tomorrow (163.com)
目录
🎂两数相加
🚩删除链表倒数第 N 个节点
AC 双指针
AC 栈
AC 计算链表长度
🌼两两交换链表中的节点
AC 递归
AC 迭代
🌼K 个一组翻转链表
🎂两数相加
2. 两数相加 - 力扣（LeetCode）
1）l1, l2 长度可能不一样，假设短的后面全是 0，通过三目运算符得到 当前节点的值，比如
n1 = l1 ? l1->val : 02）sum = n1 + n2 + 进位，%10 当前位，/10 进位
3）注意给节点赋值方式
tail->next = new ListNode(...);4）可能漏最后一次进位，while() 结束后还要来一次
时间 O(max(m, n))，空间 O(1)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *head = nullptr, *tail = nullptr;
int temp = 0; // 进位
while (l1 || l2) {
int n1 = l1 ? l1->val : 0; // l1 的值
int n2 = l2 ? l2->val : 0;
int sum = n1 + n2 + temp;
if (!head) // 第1次
head = tail = new ListNode(sum % 10); // 注意赋值方式
else {
// tail 上一步已经初始化, 所以现在是 tail->next
tail->next = new ListNode(sum % 10); // 先给下一赋值
tail = tail->next; // 再移动
}
temp = sum / 10; // 进位
// l1, l2 向后移动
if (l1) l1 = l1->next;
if (l2) l2 = l2->next;
}
// 最后一次进位
if (temp)
tail->next = new ListNode(temp);
return head; // 不返回 tail, 防止 nullptr
}
};🚩删除链表倒数第 N 个节点
19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
注意：链表的题，如果出现 Node->next，那么这个 Node 一定不为 nullptr，否则会报错
1，双指针：一前一后，前面的先移动 n 个位置，然后开始同步移动
2，栈：思路类似双指针，最终都是遍历到待删除节点前一个（从栈顶开始出栈）
3，链表长度：思路类似前面，借助哑节点，避免对删除头节点的处理，遍历两次即可
AC 双指针
时间 O(L)，空间 O(1)，L 链表长度
自己写的
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *fast = head, *slow = head;
// 前后指针 -- 找到倒数第 n 个节点, 即 slow
while (n--)
fast = fast->next;
// 删除头节点
if (!fast) {
ListNode *temp = head;
head = temp->next;
delete temp;
return head;
}
while (fast->next)
slow = slow->next, fast = fast->next;
// 删除 slow 下一节点
ListNode *bad = slow->next; // 要删除的节点
slow->next = slow->next->next;
bad->next = nullptr;
delete bad;
// 上面处理了头节点被删除的情况，所以这里可以 return head
return head;
}
};官解重写
删除倒数第 n 个节点，通过指针的 next 来操作，最后的 delete 只是为了手动释放堆区数据（自己new的自己delete）
bad 的作用是，防止删的是第一个元素，因为最终会遍历到删除节点的前一个
如果不用 bad，就像前面的代码一样，特殊处理删除节点是头节点的情况
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
// 初始化 head 上一位置, bad->next = head
ListNode *bad = new ListNode(0, head);
ListNode *fast = head, *slow = bad; // slow 初始化为 bad
while (n--)
fast = fast->next;
while (fast) {
fast = fast->next;
slow = slow->next;
}
// 此时 slow 位于删除节点 上一位置
slow->next = slow->next->next; // 更新连接
ListNode *ans = bad->next; // 新的头节点
delete bad;
return ans; // 返回新的头节点
}
};AC 栈
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
stack<ListNode *> s;
// temp 的作用是，防止删的是第一个元素，因为最终会遍历到删除节点的前一个
ListNode *temp = new ListNode(0, head);
ListNode *cur = temp;
// 链表节点全部入栈
while (cur) {
s.push(cur); // push_back 是 vector
cur = cur->next;
}
// 弹出 n 个元素后，栈顶就是待删除节点前一个
while (n--)
s.pop();
ListNode *prev = s.top();
prev->next = prev->next->next; // 先重新连接
ListNode *ans = temp->next; // 再赋值新的头节点
delete temp;
return ans;
}
};AC 计算链表长度
同样，类似上面两种，通过头节点前的，哑节点，避免对删除头节点这种情况的处理
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *temp = new ListNode(0, head); // 哑节点，避免对头节点删除的处理
ListNode *cur = temp;
int len = 0;
// 链表长度
while (cur->next) { // 长度容易错
len++;
cur = cur->next;
}
cur = temp;
int count = len - n;
// 哑节点移动 len - n + 1，即待删除节点
// 所以，移动 len - n，刚好待删除前一个
while (count--)
cur = cur->next;
cur->next = cur->next->next;
ListNode *ans = temp->next; // 新的头节点
delete temp;
return ans;
}
};🌼两两交换链表中的节点
24. 两两交换链表中的节点 - 力扣（LeetCode）
AC 递归
head之前的不用处理，举个例子，比如
转换后 head = swapPairs(temp->next)，把两两视作一个整体，那么两两中的后一个，指向哪里，取决于后面递归的结果，所以只需考虑当前层
时间 O(n)，空间 O(n)（递归栈深度 n）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
// head 表示递归时，当前两两交换节点的前一个
ListNode* swapPairs(ListNode* head) {
// 递归出口
if (head == nullptr || head->next == nullptr)
return head; // 只剩0个 或 1个节点
// 只看当前层：交换两个节点
ListNode *temp = head->next;
head->next = swapPairs(temp->next); // 递归交换剩余节点
temp->next = head;
return temp; // 返回新的头节点
}
};AC 迭代
类似冒泡排序，直接交换，但是需要借助哑节点 temp，比如
temp->Node1->Node2
👇
temp->Node2->Node1
时间 O(n)，空间 O(1)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode *temp = new ListNode(0, head); // 初始 temp->next == head
ListNode *tempHead = temp; // 头节点前一个
// 递归中的 head 是当前节点
// 迭代中的 head 只表示原链表头节点
// 所以 while 中不能用 head, 应该用 temp
while (temp->next != nullptr && temp->next->next != nullptr) {
ListNode *Node1 = temp->next;
ListNode *Node2 = temp->next->next;
// temp->Node1->Node2 ----> temp->Node2->Node1
temp->next = Node2;
Node1->next = Node2->next;
Node2->next = Node1;
// 新的哑节点
temp = Node1;
}
ListNode *ans = tempHead->next; // 新链表头节点
// delete tempHead; // 删除哑节点
return ans; // 新的头节点
}
};🌼K 个一组翻转链表
25. K 个一组翻转链表 - 力扣（LeetCode）
模拟：迭代反转 + 新建连接
以下是新建连接的 3 个步骤
k = 3 也一样
和上/下一组新建连接时，要从外层开始，就是p0->next->next到p0->next最后才是p0
p0->next->next = cur; // 下一组头 p0->next = nex; // 上一组尾 p0 = p1; // 更新p0
时间 O(n)，空间 O(1)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
// 链表长度 len
int len = 0;
for (ListNode *cur = head; cur; cur = cur->next)
len++;
// temp->next == head（temp/p0 -- 哑节点/哨兵节点）
ListNode *temp = new ListNode(0, head);
ListNode *p0 = temp; // p0 k个一组第一个节点的前一个
ListNode *nex = nullptr, *cur = head;
// k 个一组反转
for (; len >= k; len -= k) {
// 迭代 -- 反转（参考反转链表I）
// 因为哨兵节点的存在，所以是 k 次而不是 k-1 次反转
for (int i = 0; i < k; ++i) { // k 次反转
ListNode *pre = cur->next; // pre 右移
cur->next = nex; // 反转
nex = cur; // nex 右移
cur = pre; // cur 右移
}
// 当前组 与 上一组尾&&下一组头 连接
ListNode *p1 = p0->next; // 新的p0
p0->next->next = cur; // 下一组头
p0->next = nex; // 上一组尾
p0 = p1; // 更新p0
}
return temp->next; // 返回新链表的头节点
}
};
![[leetcode] max-area-of-island](https://img-blog.csdnimg.cn/img_convert/4e8aee3f9a46c1628aa287f62da2e03c.jpeg)