【头条笔试题】两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
分析问题
由于整数是由链表存储的,且链表的每个节点都只储存一位数字,因此可以抽象出如下模型
其中链表的头节点的数值为个位,依次是十位、百位、千位·····
拆解开来,就是一位数的加法,如果相加大于9,则进一位1,小于9则不进位(进位为0)。
代码实现
- ListNode类,使用了lombok插件
@ToString public class ListNode { public int val; public ListNode next; public ListNode(int x) { val = x; } }
- 算法实现和测试用例
public class AddTwoNumbers { public static void main(String[] args) { ListNode l1 = new ListNode(2); l1.next = new ListNode(4); l1.next.next = new ListNode(3); ListNode l2 = new ListNode(5); l2.next = new ListNode(6); l2.next.next = new ListNode(4); AddTwoNumbers test = new AddTwoNumbers(); System.out.println(test.addTwoNumbers(l1, l2)); } public ListNode addTwoNumbers(ListNode l1, ListNode l2) { if (l1 == null && l2 == null) { return null; } int a, b; // 存储进位数据 int carry = 0; ListNode resultNode = new ListNode(0); // 当前节点 ListNode currNode = resultNode; int sum = 0; // 遍历链表 while (l1 != null || l2 != null) { if (l1 == null) { a = 0; } else { a = l1.val; l1 = l1.next; } if (l2 == null) { b = 0; } else { b = l2.val; l2 = l2.next; } ListNode nextNode; sum = a + b + carry; if (sum > 9) { nextNode = new ListNode(sum - 10); carry = 1; } else { nextNode = new ListNode(sum); carry = 0; } // 保存next节点,切换当前节点 currNode.next = nextNode; currNode = nextNode; } // 最高位有进位 if (carry == 1) { ListNode node = new ListNode(1); currNode.next = node; } // 去除头部假节点 return resultNode.next; } }
复杂度分析
时间复杂度
时间复杂度在于对链表的遍历。假设l1的长度是 m, l2 的长度是 n,则时间复杂度为O(max(m,n))
空间复杂度
空间复杂度取决于新链表的长度,由于头结点数据无效,所以空间复杂度为O(max(m,n) + 1)