两个链表相加生成相加链表

描述

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。

给定两个这种链表，请生成代表两个整数相加值的结果链表。

例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。

示例1

输入：

[9,3,7],[6,3]

返回值：

{1,0,0,0}

备注：

$1 \leq n, m \leq 10^6$
$0 \leq a_i, b_i \leq 9$

import java.util.*;
public class Solution {

    public ListNode addInList (ListNode head1, ListNode head2) {
        
        ListNode p1 = head1;
        ListNode pre1 = null;
        
        ListNode p2 = head2;
        ListNode pre2 = null;
        // 反转第一个链表
        while(p1!= null){
            ListNode nex = p1.next;
            p1.next = pre1;
            pre1 = p1;
            p1 = nex;
        }
        head1 = pre1;
        // 反转第二个链表
        while(p2!=null){
            ListNode nex = p2.next;
            p2.next = pre2;
            pre2 = p2;
            p2 = nex;
        }
        head2 = pre2;
        // 公共长度求和
        ListNode dummyNode = new ListNode(0);
        ListNode curr = dummyNode;
        int bit = 0;
        while(head1!=null&&head2!=null){
            int val = head1.val+head2.val+bit;
            if(val>9){
                bit = 1;
                val = val%10;
            }else{
                bit = 0;
            }
            curr.next = new ListNode(val);
            curr = curr.next;
            head1 = head1.next;
            head2 = head2.next;
        }
        // 剩余长度求和
        while(head1!=null){
            int val = head1.val+bit;
            if(val>9){
                bit = 1;
                val = val%10;
            }else{
                bit = 0;
            }
            curr.next = new ListNode(val);
            curr = curr.next;
            head1 = head1.next;
        }
        // 剩余长度求和        
        while(head2!=null){
            int val = head2.val+bit;
            if(val>9){
                bit = 1;
                val = val%10;
            }else{
                bit = 0;
            }
            curr.next = new ListNode(val);
            curr = curr.next;
            head2 = head2.next;
        }
        if(bit!=0){
            curr.next = new ListNode(bit);
            curr = curr.next;
        }
        ListNode head = null;
        ListNode cur = dummyNode.next;
        // 把结果链表反转回来
        while(cur!=null){
            ListNode nex = cur.next;
            cur.next = head;
            head = cur;
            cur = nex;
        }
        
        
        return head;
    }
}

赏

谢谢你请我吃糖果

微信