两数相加Ⅱ【LC445】
给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
可以假设除了数字 0 之外，这两个数字都不会以零开头。
原来是专题模拟
反转链表
2022/11/4
- 思路：将链表1、链表2反转后进行求和，并使用变量记录进位，最后将结果再进行反转后返回
- 实现
- 如果有一个链表为空链表，那么将另一个链表返回
- 将链表1、链表2反转得到新的头结点cur1、cur2
- 使用变量cnt记录低位节点相加后的进位结果，使用cur记录求和后的结果
- 当两个链表不都为空时，需要进行累加
(val1+val2+cnt)%10得到新节点
- 注意：需要处理空节点，空节点的值记为0
- 更新：cnt = (val1+val2+cnt)/10
- 最后判断是否存在进位，如果存在的话加在链表末尾
- 最后将结果进行反转
- 代码
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { if (l1 == null){ return l2; } if (l2 == null){ return l1; } ListNode cur1 = reverse(l1); ListNode cur2 = reverse(l2); int cnt = 0; ListNode dummyNode = new ListNode(0); ListNode cur = dummyNode; while (cur1 != null || cur2 != null){ int val1 = cur1 == null ? 0 : cur1.val; int val2 = cur2 == null ? 0 : cur2.val; cur.next = new ListNode((cnt + val1 + val2) % 10); cnt = (cnt + val1 + val2 ) / 10; cur1 = cur1 == null ? null : cur1.next ; cur2 = cur2 == null ? null : cur2.next ; cur = cur.next; } if (cnt != 0){ cur.next = new ListNode(cnt); } return reverse(dummyNode.next); } public ListNode reverse(ListNode head){ ListNode dummyNode = new ListNode(0,head); ListNode cur = dummyNode.next; while (cur != null && cur.next != null){ ListNode nextTemp = cur.next.next; cur.next.next = dummyNode.next; dummyNode.next = cur.next; cur.next = nextTemp; } return dummyNode.next; } }
复杂度分析
- 时间复杂度：O(N+M)，其中 N和M分别是链表中的节点数。
- 空间复杂度：O(1)，返回值不计入空间复杂度
前后双指针
2022/11/5
思路：使用前后双指针将链表中的两数之后记录在数组中，然后倒序遍历数组，处理产生的进位，最后通过数组生成链表
实现
先将两个链表遍历一遍，统计其节点个数，记为n1,n2，使用数组nums记录数值
然后设置指针位于链表的起点，记为cur1，cur2
如果n1 > n2，那么将cur1先移动n1-n2步，并将数值记录在nums中
如果n2 > n1，那么将cur2先移动n1-n2步，并将数值记录在nums中
此时cur1和cur2位于相同位置，将链表中的两数进行相加操作，并将数值（val1+val2）记录在nums中
使用变量cnt记录低位的进行，然后倒序遍历数组处理进位
判断是否存在最高位进位，如果存在的话加在链表开头
最后通过nums数组构建链表
代码
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { if (l1 == null){ return l2; } if (l2 == null){ return l1; } ListNode cur1 = l1; ListNode cur2 = l2; int n1 = 0, n2 = 0; // 统计个数 while (cur1 != null){ n1++; cur1 = cur1.next; } while (cur2 != null){ n2++; cur2 = cur2.next; } cur1 = l1; cur2 = l2; int i = 0; int[] nums; // 移动后指针 if (n1 > n2){ nums = new int[n1]; while (i < n1 - n2){ nums[i++] = cur1.val; cur1 = cur1.next; } }else { nums = new int[n2]; while (i < n2 - n1){ nums[i++]= cur2.val; cur2 = cur2.next; } } // 链表相加 while (cur1 != null && cur2 != null){ nums[i++] = cur1.val + cur2.val; cur1 = cur1.next; cur2 = cur2.next; } // 处理进位 int cnt = 0; for (i = nums.length - 1; i >= 0;i--){ int tmp = (nums[i] + cnt) / 10; nums[i] = (nums[i] + cnt) % 10; cnt = tmp; } // 构造链表 ListNode dummyNode = new ListNode(0); ListNode cur = dummyNode; if (cnt != 0){ cur.next = new ListNode(cnt); cur = cur.next; } for(i = 0; i < nums.length; i++){ cur.next = new ListNode(nums[i]); cur = cur.next; } return dummyNode.next; } }
杂度分析
时间复杂度：O(N+M)，其中 N和M分别是链表中的节点数。
空间复杂度：O(N+M)，返回值不计入空间复杂度
栈
2022/11/5
思路：由于链表中数位的顺序与加法的顺序相反，为了逆序处理所有数位，可以使用栈，把所有数字压入栈中，再依次取出相加，计算过程中注意进位的情况
实现：倒序构建链表，注意使用变量记录当前节点的下一节点，完成链表的构建
class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { if (l1 == null){ return l2; } if (l2 == null){ return l1; } ListNode cur1 = l1; ListNode cur2 = l2; Deque<ListNode> st1 = new LinkedList<>(); Deque<ListNode> st2 = new LinkedList<>(); while (cur1 != null ){ st1.addFirst(cur1); cur1 = cur1.next; } while (cur2 != null){ st2.addFirst(cur2); cur2 = cur2.next; } int cnt = 0; ListNode nn = null; while (!st1.isEmpty() || !st2.isEmpty() || cnt != 0){ int val1 = st1.isEmpty() ? 0 :st1.pollFirst().val; int val2 = st2.isEmpty() ? 0 :st2.pollFirst().val; int val = (val1 + val2 + cnt) % 10; cnt = (val1 + val2 + cnt) / 10; ListNode ptr = new ListNode(val); ptr.next = nn; nn = ptr; } return nn; } }
