Add Two Numbers

出处

Given two linked lists, each element of the lists is a integer. Write a function to return a new list, which is the “sum” of the given two lists.

• Part a. Given input (7->1->6) + (5->9->2), output 2->1->9.
• Part b. Given input (6->1->7) + (2->9->5), output 9->1->2.

Solution

对于a，靠前节点的解不依赖靠后节点，因此顺序遍历求解即可。对于b，靠前节点的解依赖于靠后节点(进位)，因此必须用递归或栈处理。并且，子问题返回的结果，可以是一个自定义的结构(进位 + sub-list)。当然，对于问题b，也可以通过逆向列表之后再用a的解法求解。同时，注意到该题还是处理两个链表的问题，所以可以先处理常规情况(两个链表都有剩下节点)，再处理边界情况(其中一个链表已经遍历完毕)。

Complexity

时间复杂度 O(n)

Code

For part a

Node addList(Node head1, Node head2){
    Node head = new Node(-1);
   int num1 = 0, count1 = 0;
   int num2 = 0, count2 = 0;
   int result = 0;

   while (head1 != null){
       num1 += head1.data * Math.pow(10,count1);
       count1++;
       head1 = head1.next;
   }

   while (head2 != null){
       num2 += head2.data * Math.pow(10,count2);
       count2++;
       head2 = head2.next;
   }
   result = num1 + num2;

   Node cur = head;

   while(result > 0){
       cur.next = new Node(result % 10);
       cur = cur.next;
       result /= 10;
   }

   return head.next;
}

---

For part b

Node addList(Node head1, Node head2){
   Node head = new Node(-1);
   int num1 = 0, count1 = 0;
   int num2 = 0, count2 = 0;
   int result = 0;

   while (head1 != null){
       num1 = num1 * 10 + head1.data;
       count1++;
       head1 = head1.next;
   }

   while (head2 != null){
       num2 = num2 * 10 + head2.data;
       count2++;
       head2 = head2.next;
   }
   result = num1 + num2;

   Node cur = head;

   while(result > 0){
       Node temp = new Node(result % 10);
       temp.next = cur.next;
       cur.next = temp;
       result /= 10;
   }

   return head.next;
}

---

cpp version

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        ListNode *dummy = new ListNode(0), *p = dummy;
        int carry = 0;
        while(l1 || l2 || carry) {
            if(l1) {
                carry+=l1->val;
                l1 = l1->next;
            }
            if(l2) {
                carry+=l2->val;
                l2 = l2->next;
            }
            p->next = new ListNode(carry%10);
            carry /= 10;
            p = p->next;
        }
        return dummy->next;
    }
};