NC40 两个链表生成相加链表

NC40 两个链表生成相加链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    /*
     1.翻转链表
     2.每一位相加
     3.相加之后%10，/10
     4.进位之后再相加
     */
    ListNode* ReverseList(ListNode* head){
        if(head == nullptr || head->next == nullptr)
            return head;
        ListNode* pre = head;
        ListNode* cur = head->next;
        ListNode* nx = cur->next;
        pre->next = nullptr;
        while(cur != nullptr){
            cur->next = pre;
            pre = cur;
            cur = nx;
            if(nx != nullptr)
                nx = nx->next;
        }
        head = pre;
        return head;
    }
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        head1 = ReverseList(head1);
	    head2 = ReverseList(head2);
	    int val = 0;
	    int n1 = 0, n2 = 0;
	    int val1 = 0, val2 = 0;
	    ListNode new_head(-1);
	    ListNode* cur = &new_head;

	    while (head1 != nullptr || head2 != nullptr)
	    {
	    	val1 = head1 == nullptr ? 0 : head1->val; 
	    	val2 = head2 == nullptr ? 0 : head2->val;
	    	
	    	val = val1 + val2 + n2;
	    	n1 = val % 10;
	    	n2 = val / 10;
	    	ListNode* new_node = new ListNode(n1);
	    	cur->next = new_node;
	    	cur = new_node;
	    	if (head1 != nullptr)
	    		head1 = head1->next;
	    	if (head2 != nullptr)
	    		head2 = head2->next;
	    }
	    if (n2 > 0)
	    {
	    	ListNode* new_node = new ListNode(n2);
	    	cur->next = new_node;
	    	cur = new_node;
	    }
	    ListNode* ans = ReverseList(new_head.next);
	    return ans;
    }
};