2025年8月8日
小结：省流，写了俩道巨简单的（被卡好久的传参指针和指针的引用的区别），一题递归（意满）；这笔记还是0809写的，啧，今天可能不写了，明天也可能不写

LeetCode

21. 合并两个有序链表

21. 合并两个有序链表
就是一个玩指针的小小题目，啧，指针都改不明白

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode *tmp1 = list1, *tmp2 = list2, *tmp, *pre1 = nullptr;if (tmp1 == nullptr) return tmp2;else if (tmp2 == nullptr) return tmp1;// 我要返回list1，链头单列考虑if (tmp1->val >= tmp2->val) {ListNode* next2 = tmp2->next;tmp2->next = list1;list1 = tmp2;tmp2 = next2;pre1 = list1;}while (tmp1 != nullptr && tmp2 != nullptr){if (tmp1->val >= tmp2->val) {// 把2接到1当前的前面去pre1->next = tmp2;pre1 = tmp2;tmp = tmp2->next;pre1->next = tmp1;tmp2 = tmp;} else {pre1 = tmp1;tmp1 = tmp1->next;}}if (tmp1 == nullptr) {pre1->next = tmp2;} return list1;}
};

2. 两数相加

题目
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

俺不中了，俺没看到逆序，还大张旗鼓反转链表，还没用那个常用的交换反转法（下附 reverse），用头插法，然后就错了（后附传指针和指针引用的区别）

ListNode* reverse(ListNode* head) {ListNode* prev = nullptr;ListNode* curr = head;while (curr != nullptr) {ListNode* nextTmp = curr->next;curr->next = prev;prev = curr;curr = nextTmp;}return prev;
}

传指针和指针的引用，区别辨析
一个插了 1 2 3 4 5 的链表，现在试图在最开头插入 6

传指针，无引用

void insert(ListNode* head, ListNode* tmp) {tmp->next = head;head = tmp;
}ListNode* tmp = new ListNode(6);
insert(head, tmp);
打印head及后续：1 2 3 4 5

可见，未更新主函数 head

传指针的引用

void insert(ListNode* &head, ListNode* tmp) {tmp->next = head;head = tmp;
}ListNode* tmp = new ListNode(6);
insert(head, tmp);
打印head及后续：6 1 2 3 4 5

继续看这个试图头插法的反转为啥不对

void insert(ListNode* &head, ListNode* tmp) {tmp->next = head;head = tmp;
}int main() {// 创建以head开头的 5 个节点的 链表// init...ListNode *hp = head, *next = hp->next;while(next != nullptr) {insert(hp, next);next = next->next;}

分析，insert 中 next 没有更新，但是 insert 里把 next 的 next = head 了（初始就是1）
那我本来是想在 1 前面插 2，现在好了，insert 完头变成 2 了，next(第一次是2) = next->next(1) 一下
那不是又去1插2前面，妥妥死循环了

唉😔你真想改，就这样，提前存了 tmp = next->next;

ListNode *hp = head, *next = hp->next, *origin_head = head;
while(next != nullptr) {tmp = next->next;insert(head, next);next = tmp;
}
origin_head->next = nullptr; //因为1没斩断指向2的

把题目读懂后的代码（蠢货，它不用反转，啧啧啧）

class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {// 我要返回 l1int carry = 0, value;ListNode *p1 = l1, *p2 = l2, *pre;while(p1 != nullptr && p2 != nullptr) {value = p1->val + p2->val + carry;carry = value / 10;p1->val = value % 10;pre = p1;p1 = p1->next, p2 = p2->next;// cout << "value= " << value << endl;}ListNode *p;if (p1 != nullptr) {p = p1;} else {p = p2;}pre->next = p;while(p != nullptr) {value = p->val + carry;// cout << "value= " << value << endl;carry = value / 10;p->val = value % 10;pre = p;p = p->next;if (carry == 0) break;}// cout << pre->val << endl;if (carry != 0) {pre->next = new ListNode();pre->next->val = carry;}return l1;}
};

19. 删除链表的倒数第N个结点

题目
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

聪明蛋，一下子就想到递归，回头的时候把目标删了，调了一会儿，写的略丑

class Solution {
public:int find(ListNode* &now, ListNode* pre, int cnt) {if (now == nullptr) {// 说明是倒数第一个return 1;}int now_cnt = find(now->next, now, cnt) + 1;if (cnt == now_cnt - 1) {// 当前这个不要if (pre != nullptr) pre->next = now->next;else now = now->next;}return now_cnt;}ListNode* removeNthFromEnd(ListNode* head, int n) {int val = find(head, nullptr, n);// cout << "val= " << val << endl;if(val == 2) return nullptr;else return head;}
};