2. 两数相加 - 力扣（LeetCode）

高精度加法，用vector保存两个操作数，进行高精度加法后，将保存结果的vector转换成链表即可

/**
 * 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:
    void dfs(ListNode *cur, vector<int> &x)
    {
        if (cur == nullptr) return;
        x.push_back(cur->val);
        dfs(cur->next, x);
    }
    vector<int> add(vector<int> &a, vector<int> &b)
    {
        vector<int> c;
        int x = 0;
        for (int i = 0, j = 0; i < a.size() || j < b.size() || x; i ++, j ++)
        {
            if (i < a.size()) x += a[i];
            if (j < b.size()) x += b[j];
            c.push_back(x % 10);
            x /= 10;
        }
        return c;
    }
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        vector<int> a, b;
        dfs(l1, a), dfs(l2, b);
        
        vector<int> c = add(a, b);
        ListNode *ans = new ListNode;
        ListNode *cur = ans;
        for (int i = 0; i < c.size(); ++ i)
        {
            cur->val = c[i];
            if (i < c.size() - 1) cur->next = new ListNode;
            cur = cur->next;
        }
        return ans;
    }
};

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

类似后序遍历，dfs记录当前节点是倒数第几个节点
需要维护当前节点的pre节点，以及head指针的引用：要删除的节点是第一个节点时，直接修改head指针

/**
 * 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:
    void dfs(ListNode *&head, ListNode *pre, ListNode *cur, int n, int &x)
    {
        if (cur == nullptr) return;
        dfs(head, cur, cur->next, n, x);
        x ++ ;
        if (x == n)
        {
            if (pre == nullptr) head = cur->next;
            else pre->next = cur->next;
            delete cur;
            return;
        }
    }
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if (n == 1 && head->next == nullptr) return nullptr;
        int x = 0;
        dfs(head, nullptr, head, n, x);
        return head;
    }
};