题解 | #链表相加(二)#

import java.util.*;
public class Solution {

    public ListNode addInList (ListNode head1, ListNode head2) {

        if (head1 == null && head2 == null) return null;
        if (head1 == null) return head2;
        if (head2 == null) return head1;

        // 先将链表反转
        head1 = rever(head1);
        head2 = rever(head2);

        ListNode c1 = head1;
        ListNode c2 = head2;
        // 新头节点
        ListNode phead = new ListNode(0);
        ListNode ret = phead;

        int carry = 0;//进位

        //进位也要不等于0
        while (c1 != null || c2 != null || carry != 0) {
            int val1 = c1 == null ? 0 : c1.val;
            int val2 = c2 == null ? 0 : c2.val;
            int t = val1 + val2 + carry;
            // 取进位
            carry = t / 10;
            int g = t % 10;
            ListNode tmp = new ListNode(g);
            phead.next = tmp;
            phead = phead.next;

            // 不为空时才能后移
            if(c1!=null)c1 = c1.next;
            if(c2!=null)c2 = c2.next;
        }

        // 此处不能用phead，phead已经移到最后了
        return rever(ret.next);
    }

    public ListNode rever(ListNode head){
        if(head ==null) return null;
        ListNode newHead = null;
        ListNode tmp = head;
        ListNode cur = head;

        while(cur!=null){
            tmp = cur.next;
            cur.next = newHead;
            newHead = cur;
            cur = tmp;
        }
        return newHead;
    }
}