题解 | #两个链表生成相加链表#
两个链表生成相加链表
http://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b
记下来,坑很多不能大意,首先就是模拟进位加法而不是直接转化为int!,然后注意要翻转列表,因为进位加法从低位开始运算,然后是要熟悉进位加法,尤其是进位不要忘记了!
#include <stack>
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
ListNode* reverse(ListNode* head){
ListNode *next = head->next;
head->next = NULL;
while(next != NULL){
ListNode* nextnext = next->next;
next->next = head;
head = next;
next = nextnext;
}
return head;
}
ListNode* addInList(ListNode* head1, ListNode* head2) {
// write code here
if(head1 == NULL)
return head2;
if(head2 == NULL)
return head1;
head1 = reverse(head1);
head2 = reverse(head2);
ListNode* head = NULL;
ListNode* cur = NULL;
int jin = 0;
while(head1 != NULL and head2 != NULL){
int val1 = head1->val;
int val2 = head2->val;
int sum = val1 + val2 + jin;
jin = sum / 10;
int remain = sum % 10;
ListNode* next = new ListNode(remain);
if(head == NULL){
head = next;
cur = next;
}
else{
cur->next = next;
cur = next;
}
head1 = head1->next;
head2 = head2->next;
}
while(head1 != NULL){
int sum = head1->val + jin;
int remain = sum % 10;
jin = sum / 10;
ListNode* next = new ListNode(remain);
cur->next = next;
cur = next;
head1 = head1->next;
}
while(head2 != NULL){
int sum = head2->val + jin;
int remain = sum % 10;
jin = sum / 10;
ListNode* next = new ListNode(remain);
cur->next = next;
cur = next;
head2 = head2->next;
}
if(jin != 0){
ListNode* next = new ListNode(jin);
cur->next = next;
cur = next;
}
head = reverse(head);
return head;
}
};