1、链表类算法题常用技巧
【技巧】
- 画图:直观 + 形象 + 便于理解。
- 引入虚拟头节点:链表类型算法题通常是不带头节点的单向链表,从第一个位置开始存储有效数据。引入不存储数据的哨兵节点,便于处理边界情况,方便操作。
- 大胆定义变量:直接定义指针保存节点,避免担心语句执行顺序导致丢失。
- 快慢双指针:适用于判断链表是否有环、找环入口、找倒数第 n 个节点。
【链表中的常用操作】
- 创建一个新节点
new。- 尾插:先定义变量指向尾节点,
tail->next = 新节点,tail指向新节点(初始化时尾指针指向最后一个节点)。- 头插:使用虚拟头节点,让新节点的
next指向虚拟头节点的next,然后让虚拟头节点的next指向新节点。头插法可直接用于逆序链表。*只需定义一个
cur,再完成头插即可实现逆序链表。【注意】链表题一定要特别注意空节点!*
2、2.两数相加

题目解析:
输入为逆序存储的链表数字,例如 342+465=807,返回 708。逆序存储方便从最低位开始相加,对应链表的低位节点。
思路:
先创建虚拟头节点 newhead,初始化 t 用来存储两数加的结果。将 cur1 和 cur2 的值累加到 t 中,求出 t 的个位,创建新节点放入结果链表尾部。

/** * 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* cur1 = l1, *cur2 = l2; ListNode* newhead = new ();






