题目:
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
解题思路:
两个链表中的元素相加相比普通的加法操作增加了一个层次,和两个数组中的元素相加意义上差不多,这个题可以引申到大数相加上。需要注意的是:进位的处理。
代码展示:
1 #include <iostream>
2 #include <cassert>
3
4 using namespace std;
5
6
7 //Definition for singly-linked list.
8 struct ListNode {
9 int val;
10 ListNode *next;
11 ListNode(int x) : val(x), next(NULL) {}
12 }; 13 14 ListNode * insertNodes(int n) 15 { 16 ListNode *pNode = new ListNode(0); 17 ListNode *p = pNode; 18 int i = 0; 19 int m; 20 while(i < n) { 21 cin >> m; 22 ListNode *pIn = new ListNode(m); 23 p->next = pIn; 24 p = pIn; 25 26 i++; 27 } 28 return pNode->next; 29 } 30 31 void Print(ListNode *p) 32 { 33 ListNode *pT = p; 34 while(NULL != pT) { 35 cout << pT->val << " "; 36 pT = pT->next; 37 } 38 } 39 40 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 41 { 42 assert(NULL != l1); 43 assert(NULL != l2); 44 45 ListNode *pRetNode = new ListNode(0); 46 ListNode *p = pRetNode; 47 48 int div = 0; 49 int nSumVal; 50 while (NULL != l1 || NULL != l2) { 51 int val1 = 0, val2 = 0; 52 if (NULL != l1) { 53 val1 = l1->val; 54 l1 = l1->next; 55 } 56 if (NULL != l2) { 57 val2 = l2->val; 58 l2 = l2->next; 59 } 60 nSumVal = val1 + val2 + div; //一个比较巧妙的进位相加的方式 61 div = nSumVal/10; 62 ListNode *pT = new ListNode(nSumVal%10); 63 p->next = pT; 64 p = pT; 65 } 66 if (div) { 67 p->next = new ListNode(div); 68 } 69 return pRetNode->next; 70 } 71 72 // int main() 73 // { 74 // ListNode *p1 = insertNodes(1); 75 // ListNode *p2 = insertNodes(4); 76 // ListNode *p = addTwoNumbers(p1,p2); 77 // Print(p); 78 // return 0; 79 // }