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; } };
链表题打牢基础的话,对后续数据结构的理解也有很大帮助,建议大家多多练习,题目旁的链接点进去即可挑战!