2、AB10 ~ AB11题解 题目链接：合并两个排序链表 2.1、解题思路 新创建一个链表，根据已知的两个递增链表的元素大小来升序的在新链表中存储数据 头插法建表，使用另外的链表指针作为辅助 当两个已知链表有一个已经遍历完时，直接让辅助指针指向非空的链表结点即可 2.2、代码实现及注释 本题源码： /* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { ListNode* vhead = new ListNode(-1); ListNode* cur = vhead; while (pHead1 && pHead2) { if (pHead1->val <= pHead2->val) { cur->next = pHead1; pHead1 = pHead1->next; } else { cur->next = pHead2; pHead2 = pHead2->next; } cur = cur->next; } cur->next = pHead1 ? pHead1 : pHead2; return vhead->next; } }; 重要注释： new ListNode(-1) 相当于创建了一个头结点，cur作为头插的赋值指针 while循环内部为头插法建立升序链表的过程 三目运算符目的是让新链表的尾指向剩余链表的头 最后返回的时候不需要头结点，因此结果为vhead->next 反转链表解析的博文地址：反转链表及进阶 反转链表的题目中我用了vector容器自带的reverse方法，非常适合入门新手 3、AB12 删除链表的节点 题目链接：删除链表节点 3.1、解题思路 观察链表的定义代码可知，该题链表是没有头结点的，那么就可以分情况讨论： 若链表第一个结点的值为目标值，直接返回结点的下一个指向即可 若链表首结点不是目标值，将其当作头结点即可，使用两个移动指针的方法： 步骤与本文上面 模板链表 步骤几乎一致，不做赘述 3.2、代码实现 /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param head ListNode类 * @param val int整型 * @return ListNode类 */ ListNode* deleteNode(ListNode* head, int val) { ListNode* ptr = head->next; if(head->val==val) return ptr; ListNode* pre = head; while (ptr) { if (ptr->val == val) { if (ptr->next) { pre->next = ptr->next; break; } else { pre->next = NULL; } } else { pre = ptr; ptr = ptr->next; } } return head; } }; 链表题打牢基础的话，对后续数据结构的理解也有很大帮助，建议大家多多练习，题目旁的链接点进去即可挑战！