【链表相加】程序员面试金典——2.5链式A+B

Solution1：我的答案

普通思路，注意：在构造链表时，可以充分利用不存储有效数据的头结点，这样会使代码写的比较简练！

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ class Plus { public: ListNode* plusAB(ListNode* a, ListNode* b) { // write code here int res = list_to_num(a) + list_to_num(b); return num_to_list(res); } int list_to_num(struct ListNode* pHead) { int res = 0, base = 1; struct ListNode* cur = pHead; while(cur != NULL) { res += cur->val * base; cur = cur->next; base *= 10; } return res; } struct ListNode* num_to_list(int n) { struct ListNode* pHead = new ListNode(-1); struct ListNode* cur = pHead; while(n !=0 ) { cur->next = new ListNode(n); cur = cur->next; n /= 10; } return pHead->next; } };

Solution2：

参考网址：https://www.nowcoder.com/profile/5370192/codeBookDetail?submissionId=15262903 本题的思路很简单，按照小学数学中学习的加法原理从末尾到首位，对每一位对齐相加即可。技巧在于如何处理不同长度的数字，以及进位和最高位的判断。这里对于不同长度的数字，我们通过将较短的数字补0来保证每一位都能相加。 20181008整理代码

class Plus { public: ListNode* plusAB(ListNode* a, ListNode* b) { // 头结点 ListNode *head = new ListNode(-1); ListNode *p = head; ListNode *node = NULL; int c = 0, sum, val1, val2; ListNode *pa = a, *pb = b; //加法 while (pa || pb || c) { val1 = (pa == NULL ? 0 : pa->val); val2 = (pb == NULL ? 0 : pb->val); sum = val1 + val2 + c; // 进位 c = sum / 10; node = new ListNode(sum % 10); //尾插法 p->next = node; p = node; pa = (pa == NULL ? NULL : pa->next); pb = (pb == NULL ? NULL : pb->next); }//while return head->next; } };

原答案

class Plus { public: ListNode* plusAB(ListNode* a, ListNode* b) { // 头结点 ListNode *head = new ListNode(-1); ListNode *p = head; ListNode *node = nullptr; int c = 0,sum,val1,val2; ListNode *pa = a,*pb = b; //加法 while(pa != nullptr || pb != nullptr || c != 0){ val1 = (pa == nullptr ? 0 : pa->val); val2 = (pb == nullptr ? 0 : pb->val); sum = val1 + val2 + c; // 进位 c = sum / 10; node = new ListNode(sum % 10); //尾插法 p->next = node; p = node; pa = (pa == nullptr ? nullptr : pa->next); pb = (pb == nullptr ? nullptr : pb->next); }//while return head->next; } };