给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

没啥好说的,加就完事了,如果相加大于十就向下一位进1(一位数字相加最大值9+9=18,进位的数字最多为1)。解法:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {    
        if(l1==null||l2==null){
            return null;
        }
        ListNode dhead = new ListNode(-1);
        ListNode p1 = l1,p2=l2,cur = dhead;
        int isplus = 0;
        while(p1!=null||p2!=null){
            int x = (p1!=null)?p1.val:0;
            int y = (p2!=null)?p2.val:0;
            int sum = x+y+isplus;
            isplus = sum/10;
            cur.next = new ListNode(sum%10);
            cur = cur.next;
            if(p1!=null){
                p1 = p1.next;
            }
            if(p2!=null){
                p2 = p2.next;
            }
        }
        
        if(isplus>0){
            cur.next = new ListNode(isplus);
        }
        return dhead.next;
    }
}

此题还有一个变种(今日头条笔试时遇到过),那就是两个链表正序相加。

哈哈哈,我不知道别人是怎么做的,我是先将链表进行了反转,将反转后的链表倒序相加,最后将得到的链表再次反转即可得到结果。(关于反转链表)

Last modification:April 30th, 2019 at 03:58 am
大家一起分享知识,分享快乐