链表基础算法总结与经典题目解析

一、链表常用技巧和操作总结

有关链表的算法题是一类常见并且经典的题型，这些题要使用数据结构中手搓的链表结构，也要使用 STL 中的 list 容器。

下面是几点常用操作的总结：

1. 善于画图。
2. 引入虚拟头结点。方便处理边界情况，就是当没有节点第一次头插或尾插的时候的那个判断，引入虚拟头结点就可以避免这个判断（写成 ptail = newHead）。
3. 不要吝啬空间，大胆定义变量。
4. 快慢双指针的使用。主要应用是判环，找链表中环的入口，找链表中倒数第 n 个节点。
5. 解决链表类的题，一般是：创建一个新节点，尾插操作，头插操作。

二、算法原理和代码实现

2. 两数相加

算法原理：

这道题是一道简单的模拟题，模拟两数相加即可。定义两个指针 cur1 和 cur2 用于遍历两个链表，再定义一个整数 t 用于进位。用 t 和每个节点的值相加，取出 t 的个位创建新节点。

细节问题：

1. 这里要注意的细节就是链表是逆序的，其实这也是方便我们操作，因为我们可以直接从个位开始相加。
2. 循环条件：cur1 || cur2 || t。这里要或 t 是原因：当两个指针都走完时，t 里可能还有进位，还需要尾插。
3. 要销毁哨兵位头节点。

代码实现：

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;
    }
};