【宫水三叶の真题精选】链表模拟题（含哨兵技巧运用）

朴素解法（哨兵技巧）

这是道模拟题，模拟人工竖式做加法的过程：

从最低位至最高位，逐位相加，如果和大于等于 10，则保留个位数字，同时向前一位进 1 如果最高位有进位，则需在最前面补 1。

做有关链表的题目，有个常用技巧：添加一个虚拟头结点（哨兵），帮助简化边界情况的判断。

一些细节：由于给定的两个数值是按照「从高位到低位」进行存储，但我们的计算过程是「从低位到高位」进行，因此在进行计算前，应当先对链表进行翻转。同时，在计算完成后，再对答案链表进行。

代码：

import java.util.*;

public class Solution {
    ListNode reverse(ListNode root) {
        ListNode prev = null, cur = root;
        while (cur != null) {
            ListNode tmp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = tmp;
        }
        return prev;
    }
    public ListNode addInList (ListNode head1, ListNode head2) {
        ListNode l1 = reverse(head1), l2 = reverse(head2);
        ListNode dummy = new ListNode(0);
        ListNode tmp = dummy;
        int t = 0;
        while (l1 != null || l2 != null) {
            int a = l1 != null ? l1.val : 0;
            int b = l2 != null ? l2.val : 0;
            t = a + b + t;
            tmp.next = new ListNode(t % 10);
            t /= 10;
            tmp = tmp.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        if (t > 0) tmp.next = new ListNode(t);
        return reverse(dummy.next);
    }
}

时间复杂度： $m$ 和 $n$ 分别代表两条链表的长度，则遍历到的最远位置为 $max(m,n)$ ，复杂度为 $O(max(m,n))$
空间复杂度：创建了 $max(m,n) + 1$ 个节点（含哨兵），复杂度为 $O(max(m,n))$ （忽略常数）

注意：事实上还有可能创建 $max(m + n) + 2$ 个节点，包含哨兵和最后一位的进位。但复杂度仍为 $O(max(m,n))$ 。

最后

这是我们「必考真题の精选」系列文章的第 No.40 篇，系列开始于 2021/07/01。

该系列会将牛客网中「题霸 - 面试必考真题」中比较经典而又不过时的题目都讲一遍。

在提供追求「证明」&「思路」的同时，提供最为简洁的代码。

欢迎关注，交个朋友 (｀・ω・´)