链表算法专题：常用技巧与经典题目解析

1、链表类算法题常用技巧

【技巧】

1. 画图：直观 + 形象 + 便于理解。
2. 引入虚拟头节点：链表类型算法题通常是不带头节点的单向链表，从第一个位置开始存储有效数据。引入不存储数据的哨兵节点，便于处理边界情况，方便操作。
3. 大胆定义变量：直接定义指针保存节点，避免担心语句执行顺序导致丢失。
4. 快慢双指针：适用于判断链表是否有环、找环入口、找倒数第 n 个节点。

【链表中的常用操作】

1. 创建一个新节点 new。
2. 尾插：先定义变量指向尾节点，tail->next = 新节点，tail 指向新节点（初始化时尾指针指向最后一个节点）。
3. 头插：使用虚拟头节点，让新节点的 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 ();