网站开发数据库课程设计,wordpress怎么做微博,厦门建设局人员名单,游戏网站建设杭州不要觉得力扣核心代码模式麻烦#xff0c;它确实比不上ACM模式舒服#xff0c;可以自己处理输入输出 只是你对 链表 和 return 的理解不到位 #x1f442; ▶ 屿前世 (163.com)
#x1f442; ▶ see you tomorrow (163.com) 目录
#x1f382;两数相加
#x1f6a9;删… 不要觉得力扣核心代码模式麻烦它确实比不上ACM模式舒服可以自己处理输入输出 只是你对 链表 和 return 的理解不到位 ▶ 屿前世 (163.com) ▶ see you tomorrow (163.com) 目录
两数相加
删除链表倒数第 N 个节点
AC 双指针
AC 栈
AC 计算链表长度
两两交换链表中的节点
AC 递归
AC 迭代
K 个一组翻转链表 两数相加
2. 两数相加 - 力扣LeetCode 1l1, l2 长度可能不一样假设短的后面全是 0通过三目运算符得到 当前节点的值比如 n1 l1 ? l1-val : 0 2sum 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-nexttail-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 个节点, 即 slowwhile (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 headreturn 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 headListNode *bad new ListNode(0, head); ListNode *fast head, *slow bad; // slow 初始化为 badwhile (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) {stackListNode * s;// temp 的作用是防止删的是第一个元素因为最终会遍历到删除节点的前一个ListNode *temp new ListNode(0, head);ListNode *cur temp;// 链表节点全部入栈while (cur) {s.push(cur); // push_back 是 vectorcur 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 headListNode *tempHead temp; // 头节点前一个// 递归中的 head 是当前节点// 迭代中的 head 只表示原链表头节点// 所以 while 中不能用 head, 应该用 tempwhile (temp-next ! nullptr temp-next-next ! nullptr) {ListNode *Node1 temp-next;ListNode *Node2 temp-next-next;// temp-Node1-Node2 ---- temp-Node2-Node1temp-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) {// 链表长度 lenint len 0;for (ListNode *cur head; cur; cur cur-next)len;// temp-next headtemp/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; // 新的p0p0-next-next cur; // 下一组头p0-next nex; // 上一组尾p0 p1; // 更新p0}return temp-next; // 返回新链表的头节点}
};
