2. Add Two Numbers
Medium
You are given two non-empty linked lists representing two non-negative integers. 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.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | //C++: 40ms /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode *p1 = l1, *p2 = l2; ListNode *H = new ListNode(0), *p = H; int carry = 0; while(p1 || p2 || carry){ int sum = carry; if(p1){ sum += p1->val; p1 = p1->next; } if(p2){ sum += p2->val; p2 = p2->next; } ListNode *n = new ListNode(sum%10); p->next = n; p = n; carry = sum/10; } return H->next; } }; |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | /** * 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) { ListNode p1 = l1, p2 = l2; ListNode H = new ListNode(), p = H; int c = 0; while(p1!=null || p2!=null){ if(p1!=null){ c += p1.val; p1 = p1.next; } if(p2!=null){ c += p2.val; p2 = p2.next; } ListNode n = new ListNode(c%10); p.next = n; p = n; c = c/10; } if(c!=0){ ListNode n = new ListNode(c); p.next = n; } return H.next; } } |
No comments:
Post a Comment