【算法训练-链表 五】【链表求和】：链表相加（逆序）、链表相加II（顺序）

废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！本篇Blog的主题是【链表相加】，使用【链表】这个基本的数据结构来实现，这个高频题的站点是：CodeTop，筛选条件为：目标公司+最近一年+出现频率排序，由高到低的去牛客TOP101去找，只有两个地方都出现过才做这道题（CodeTop本身汇聚了LeetCode的来源），确保刷的题都是高频要面试考的题。

名曲目标题后，附上题目链接，后期可以依据解题思路反复快速练习，题目按照题干的基本数据结构分类，且每个分类的第一篇必定是对基础数据结构的介绍。

链表相加【MID】

题干

首先来一道逆序版，稍微比较好搞一些的，因为链表只能向后遍历：

解题思路

整体思路就是遍历完两个链表进行相加并将结果集放到新的链表上

1. 设置返回链表的链表头，设置进位cnt=0.
2. 从头开始遍历两个链表，直到两个链表节点都为空：
   1. 每次取出不为空的链表节点值，为空就设置为0
   2. 将两个数字与cnt相加，就是当前的总和
   3. 将总和（对10取模）加入新的链表节点，连接在返回链表后面，并继续往后遍历，并用总和对10除获取进位值
3. 如果两个链表都遍历完成，cnt进位还有值，则补充创建一个节点，值为cnt

代码实现

给出代码实现基本档案

基本数据结构：链表
辅助数据结构：无
算法：迭代
技巧：双指针

其中数据结构、算法和技巧分别来自：

• 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
• 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
• 技巧：双指针、滑动窗口、中心扩散

当然包括但不限于以上

;
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    *
    * @param head1 ListNode类
    * @param head2 ListNode类
    * @return ListNode类
    */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // 1 先将两个链表反转过来
        ListNode p1 = head1;
        ListNode p2 = head2;

        // 2 设置结果集以及初始化进位标识符
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        int cnt = 0;

        // 3 目标是遍历完两个链表的全部长度
        while (p1 != null || p2 != null) {
            // 3-1 获取当前节点值，如果是null节点则值为0
            int d1 = p1 == null ? 0 : p1.val;
            int d2 = p2 == null ? 0 : p2.val;
            // 3-2 计算总和、进位值、当前节点值
            int curSum = d1 + d2 + cnt;
            cnt = curSum / 10;
            p.next =  new ListNode(curSum % 10);
            // 3-3 结果指针移动，节点指针移动
            p = p.next;
            p1 = p1 == null ? null : p1.next;
            p2 = p2 == null ? null : p2.next;
        }

        // 4 全部结果如果遍历完，进位值还是大于0，则设置为最后一个节点
        if (cnt > 0) {
            p.next =  new ListNode(cnt);
        }
        return dummy.next;
    }
}

复杂度分析

时间复杂度：遍历链表，时间复杂度为O（N）
空间复杂度：不算返回的结果集的话，没有用到辅助空间，所以空间复杂度为O（1）

链表相加II【MID】

题干

进阶版，值为顺序，但链表是单向的，不能反过来遍历

解题思路

虽然链表不能反过来遍历，但是我们可以开始的时候就反转链表，然后返回结果时候再反转回去

1. 任意一个链表为空，返回另一个链表就行了，因为链表为空相当于0，0加任何数为0，包括另一个加数为0的情况。
2. 相继反转两个待相加的链表，反转过程可以参考反转链表。
3. 设置返回链表的链表头，设置进位cnt=0.
4. 从头开始遍历两个链表，直到两个链表节点都为空：
   1. 每次取出不为空的链表节点值，为空就设置为0
   2. 将两个数字与cnt相加，就是当前的总和
   3. 将总和（对10取模）加入新的链表节点，连接在返回链表后面，并继续往后遍历，并用总和对10除获取进位值
5. 如果两个链表都遍历完成，cnt进位还有值，则补充创建一个节点，值为cnt
6. 返回前将结果链表再反转回来。

代码实现

给出代码实现基本档案

基本数据结构：链表
辅助数据结构：无
算法：迭代
技巧：双指针

其中数据结构、算法和技巧分别来自：

• 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
• 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
• 技巧：双指针、滑动窗口、中心扩散

当然包括但不限于以上

;
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // 1 先将两个链表反转过来
        ListNode p1 = reverse(head1);
        ListNode p2 = reverse(head2);

        // 2 设置结果集以及初始化进位标识符
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        int cnt = 0;

        // 3 目标是遍历完两个链表的全部长度
        while (p1 != null || p2 != null) {
            // 3-1 获取当前节点值，如果是null节点则值为0
            int d1 = p1 == null ? 0 : p1.val;
            int d2 = p2 == null ? 0 : p2.val;
            // 3-2 计算总和、进位值、当前节点值
            int curSum = d1 + d2 + cnt;
            cnt = curSum / 10;
            p.next =  new ListNode(curSum % 10);
            // 3-3 结果指针移动，节点指针移动
            p = p.next;
            p1 = p1 == null ? null : p1.next;
            p2 = p2 == null ? null : p2.next;
        }

        // 4 全部结果如果遍历完，进位值还是大于0，则设置为最后一个节点
        if (cnt > 0) {
            p.next =  new ListNode(cnt);
        }
        return reverse(dummy.next);
    }

    private ListNode reverse(ListNode head) {
        if (head == null) return null;
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode pNext = cur.next;
            cur.next = pre;
            pre = cur;
            cur = pNext;
        }
        return pre;
    }
}

复杂度分析

时间复杂度：遍历链表，时间复杂度为O（N）
空间复杂度：不算返回的结果集的话，没有用到辅助空间，所以空间复杂度为O（1）