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
思路:先将两个链表分别遍历一遍,获得链表长度,然后进行相加,时间复杂度为O(N)。
class Solution { public: ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) { ListNode* sum = new ListNode(INT_MAX); ListNode* root = sum; int m1 = 0; int m2 = 0; ListNode* ptr1 = l1; ListNode* ptr2 = l2; while(ptr1 != NULL) { ++m1; ptr1 = ptr1->next; } while(ptr2 != NULL) { ++m2; ptr2 = ptr2->next; } if (m1 < m2) { ptr1 = l1; l1 = l2; l2 = ptr1; m1 ^= m2; m2 ^= m1; m1 ^= m2; } ptr1 = l1; ptr2 = l2; int flag = 0,val; ListNode* pNode; while(ptr2 != NULL) { val = (ptr1->val + ptr2->val + flag ) % 10; flag = (ptr1->val + ptr2->val + flag) / 10; pNode = new ListNode(val); sum->next = pNode; sum = sum->next; ptr2 = ptr2->next; ptr1 = ptr1->next; } while(ptr1 != NULL) { val = (ptr1->val + flag) % 10; flag = (ptr1->val + flag) / 10; pNode = new ListNode(val); sum->next = pNode; sum = sum->next; ptr1 = ptr1->next; } if (flag != 0) { pNode = new ListNode(flag); sum->next = pNode; sum = sum->next; } return root->next; } };