一、链表常用技巧和操作总结
有关链表的算法题是一类常见并且经典的题型,这些题要使用数据结构中手搓的链表结构,也要使用 STL 中的 list 容器。
下面是几点常用操作的总结:
- 善于画图。
- 引入虚拟头结点。方便处理边界情况,就是当没有节点第一次头插或尾插的时候的那个判断,引入虚拟头结点就可以避免这个判断(写成
ptail = newHead)。 - 不要吝啬空间,大胆定义变量。
- 快慢双指针的使用。主要应用是判环,找链表中环的入口,找链表中倒数第 n 个节点。
- 解决链表类的题,一般是:创建一个新节点,尾插操作,头插操作。
二、算法原理和代码实现
2. 两数相加



算法原理:
这道题是一道简单的模拟题,模拟两数相加即可。定义两个指针 cur1 和 cur2 用于遍历两个链表,再定义一个整数 t 用于进位。用 t 和每个节点的值相加,取出 t 的个位创建新节点。
细节问题:
- 这里要注意的细节就是链表是逆序的,其实这也是方便我们操作,因为我们可以直接从个位开始相加。
- 循环条件:
cur1 || cur2 || t。这里要或 t 是原因:当两个指针都走完时,t 里可能还有进位,还需要尾插。 - 要销毁哨兵位头节点。
代码实现:
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* cur1 = l1, *cur2 = l2;
ListNode* newHead = new ListNode(), *ptail = newHead; // 虚拟头节点
int t = ;
(cur1 || cur2 || t) {
(cur1) { t += cur1->val; cur1 = cur1->next; }
(cur2) { t += cur2->val; cur2 = cur2->next; }
ListNode* newNode = (t % );
ptail->next = newNode;
ptail = newNode;
ptail->next = ;
t /= ;
}
ListNode* pcur = newHead->next;
newHead;
pcur;
}
};














