算法讲解011【入门】链表入门题目-两个链表相加

链表入门题目-两个链表相加大纲

• 给你两个 非空 的链表，表示两个非负的整数

• 它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字

• 请你将两个数相加，并以相同形式返回一个表示和的链表

• 你可以假设除了数字 0 之外，这两个数都不会以 0 开头

视频笔记

• 这题就是考链表的调整，不用想着绕过题目

• 先准备两个链表ans = null , cur = null，定义一个carry = 0表示s是否进位

• for 循环 终止条件， h1 和 h2都为空，每次h1和h2都会跳，到空不再跳
• 定义 sum 作为中间存储变量， val = sum %10 表示这一位数字实际结果（其实就是不管进不进为位，只要个位） ，carry=sum / 10 判断要不要进位
• 接着 if else 判断建表没有（ans是否为空），如果为空， 创建一个ans节点，存放val
• ans 只有一开始两个数字相加后，作为头节点创建，后续不再使用
• 否则让 curr.next 指向新的节点，并且这个节点存放新的 val，然后让 curr 指向 curr.next
• 如此循环，在循环判断里头，要注意如果有一个链表走完了，那么有一个 h 要为 0 ，另一个继续取节点

• 最后判断还有没有进位，如果有进位也要把它加上去，然后返回 ans

• 如图

• 第二遍看的时候想把ans节点剔除掉进行优化代码，但是我发现实际上ans节点存储的是新链表的头节点，不能剔除

• package class011;​// 给你两个 非空 的链表，表示两个非负的整数// 它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字// 请你将两个数相加，并以相同形式返回一个表示和的链表。// 你可以假设除了数字 0 之外，这两个数都不会以 0 开头// 测试链接：https://leetcode.cn/problems/add-two-numbers/public class AddTwoNumbers {​ // 不要提交这个类 public static class ListNode { public int val; public ListNode next;​ public ListNode(int val) { this.val = val; }​ public ListNode(int val, ListNode next) { this.val = val; this.next = next; } }​ class Solution {​ // 也可以复用老链表 // 不过这个实现没有这么做，都是生成的新节点(为了教学好懂) public static ListNode addTwoNumbers(ListNode h1, ListNode h2) { ListNode ans = null, cur = null; int carry = 0; for (int sum, val; // 声明变量 h1 != null || h2 != null; // 终止条件 h1 = h1 == null ? null : h1.next, // 每一步h1的跳转 h2 = h2 == null ? null : h2.next // 每一步h2的跳转 ) {​ sum = (h1 == null ? 0 : h1.val) + (h2 == null ? 0 : h2.val) + carry;​ val = sum % 10; carry = sum / 10; if (ans == null) { ans = new ListNode(val); cur = ans; } else { cur.next = new ListNode(val); cur = cur.next; } } if (carry == 1) { cur.next = new ListNode(1); } return ans; }​ }​}​