1 题目
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
接口
ListNode addTwoNumbers(ListNode l1, ListNode l2);
2 思路
链表存储整数是低位前、高位后，逐位相加，注意进位。
复杂度
Time: O(n)
Space: O(n) 因为需要O(n)的空间来储存result。
3 代码
Definition for singly-linked list.
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
dummy.next = null;
ListNode tail = dummy;
for (ListNode p1 = l1, p2 = l2; p1 != null || p2 != null;) {
int a1 = p1 == null ? 0 : p1.val;
int a2 = p2 == null ? 0 : p2.val;
int sum = dummy.val + a1 + a2;
dummy.val = sum < 10 ? 0 : 1;
tail.next = new ListNode(sum % 10);
tail = tail.next;
p1 = p1 == null ? null : p1.next;
p2 = p2 == null ? null : p2.next;
}
if (dummy.val == 1)
tail.next = new ListNode(1);
return dummy.next;
}
4 总结
- 利用头节点dummy来记录进位值，尾指针tail来构造result。
- 代码考虑到了2个链表长度不相等的情况。
- Similar as "Add Binary". The only difference is the pointer operation.
5 扩展
1.如果链表储存整数，不是逆序的，是高位前、地位后，如何解？
Input: (2 -> 4 -> 1) + (5 -> 7 -> 4)
Output: 8 -> 1 -> 5
想法：可以将input的2个链表反转，利用上面的解法求解，将结果链表在反转一次。
Time: O(n) Space:O(1).
2.如果是BigInteger的相加，数据结果不一定要用链表，也可以是数组，面试中可能两种都会问而且实现。
3.然后接下来可以考一些OO设计的东西，比如说如果这是一个类应该怎么实现，也就是把数组或者链表作为成为成员变量，再把这些操作作为成员函数，进一步的问题可能是如何设计constructor，这个问题除了基本的还得对内置类型比如int, long的constructor, 类似于BigInteger(int num), BigInteger(int long). 总体来说问题还是比较简单，但是这种问题不能出错，所以还是要谨慎对待。