【牛客题霸题解】链表相加

先把链表进行反转，然后再相加
反转链表的步骤参考NC78
https://blog.nowcoder.net/n/31e6abf3dd5d4970a03f7a483ca8e0ab
相加的时候每一位上的值等于两个链表那位上的值相加再加上之前的进位%10

c++

class Solution {
public:
    //反转链表
    ListNode* ReverseList(ListNode* pHead) {
        ListNode* Pre = NULL;
        ListNode* Now = pHead;
        ListNode* Next = NULL;
        while(Now!=NULL)
        {
            Next = Now->next;
            Now->next = Pre;
            Pre = Now;
            Now = Next;
        }
        pHead = Pre;
        return pHead;
    }
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        head1 = ReverseList(head1);
        head2 = ReverseList(head2);
        ListNode* res = new ListNode(0);
        ListNode* now = res;
        int d = 0;//存储进位
        while(head1!=NULL||head2!=NULL)
        {
            int num = d;
            if(head1!= NULL){
                num += head1->val;
                head1 = head1->next;
            }
            if(head2!= NULL){
                num += head2->val;
                head2 = head2->next;
            }
            d = num/10;
            num = num%10;
            ListNode *t = new ListNode(num);
            now->next = t;
            now = now->next;
            cout<<now->val<<endl;
        }
        if(d!=0)
        {
            ListNode t(d);
            t.next = NULL;
            now ->next = &t;
        }
        else{
            now ->next = NULL;
        }
        res = ReverseList(res->next);
        return res;
    }
};

java

import java.util.*;
public class Solution {

    public ListNode ReverseList(ListNode head) {
        ListNode Pre = null;
        ListNode Now = head;
        ListNode Next = null;
        while(Now != null){
            Next = Now.next;
            Now.next = Pre;
            Pre = Now;
            Now = Next; 
        }
        head = Pre;
        return head;
    }
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        head1 = ReverseList(head1);
        head2 = ReverseList(head2);
        ListNode res = new ListNode(0);
        ListNode now = res;
        int d = 0;//存储进位

        while(head1!=null||head2!=null)
        {
            int num = d;
            if(head1!= null){
                num += head1.val;
                head1 = head1.next;
            }
            if(head2!= null){
                num += head2.val;
                head2 = head2.next;
            }
            d = num/10;
            num = num%10;
            ListNode t = new ListNode(num);
            now.next = t;
            now = now.next;
        }
        if(d!=0)
        {
            ListNode t =new ListNode(d);
            t.next = null;
            now.next = t;
        }
        else{
            now.next = null;
        }
        res = ReverseList(res.next);
        return res;
    }
}

python

class Solution:
    def ReverseList(self, pHead):
        Pre = None
        Now = pHead
        Next = None
        while Now != None:
            Next = Now.next
            Now.next = Pre
            Pre = Now
            Now = Next
        pHead = Pre
        return pHead
    def addInList(self , head1 , head2 ):
        head1 = self.ReverseList(head1)
        head2 = self.ReverseList(head2)
        res = ListNode(0)
        now = res
        d = 0
        while head1!=None or head2!=None:
            num = d
            if head1!= None:
                num = num + head1.val
                head1 = head1.next
            if head2!= None:
                num = num+head2.val
                head2 = head2.next
            d = num//10
            num = num%10
            t = ListNode(num)
            now.next = t
            now = now.next
        if d!=0:
            t = ListNode(d)
            t.next = None
            now.next = t
        else:
            now.next = None
        res = self.ReverseList(res.next)
        return res