废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！本篇Blog的主题是【链表相加】，使用【链表】这个基本的数据结构来实现，这个高频题的站点是：CodeTop，筛选条件为：目标公司+最近一年+出现频率排序，由高到低的去牛客TOP101去找，只有两个地方都出现过才做这道题（CodeTop本身汇聚了LeetCode的来源），确保刷的题都是高频要面试考的题。
名曲目标题后，附上题目链接，后期可以依据解题思路反复快速练习，题目按照题干的基本数据结构分类，且每个分类的第一篇必定是对基础数据结构的介绍。
链表相加【MID】
题干
首先来一道逆序版，稍微比较好搞一些的，因为链表只能向后遍历：
解题思路
整体思路就是遍历完两个链表进行相加并将结果集放到新的链表上
- 设置返回链表的链表头，设置进位cnt=0.
- 从头开始遍历两个链表，直到两个链表节点都为空：
- 每次取出不为空的链表节点值，为空就设置为0
- 将两个数字与cnt相加，就是当前的总和
- 将总和（对10取模）加入新的链表节点，连接在返回链表后面，并继续往后遍历，并用总和对10除获取进位值
- 如果两个链表都遍历完成，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】
题干
进阶版，值为顺序，但链表是单向的，不能反过来遍历
解题思路
虽然链表不能反过来遍历，但是我们可以开始的时候就反转链表，然后返回结果时候再反转回去
- 任意一个链表为空，返回另一个链表就行了，因为链表为空相当于0，0加任何数为0，包括另一个加数为0的情况。
- 相继反转两个待相加的链表，反转过程可以参考反转链表。
- 设置返回链表的链表头，设置进位cnt=0.
- 从头开始遍历两个链表，直到两个链表节点都为空：
- 每次取出不为空的链表节点值，为空就设置为0
- 将两个数字与cnt相加，就是当前的总和
- 将总和（对10取模）加入新的链表节点，连接在返回链表后面，并继续往后遍历，并用总和对10除获取进位值
- 如果两个链表都遍历完成，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 = 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）
