两数相加

445. 两数相加 II

难度中等355收藏分享切换为英文接收动态反馈

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

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

进阶：

如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例：

输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7

使用栈

官方题解的思路是栈，不过原地的话应该也可以就是很麻烦

/**
 * 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) {
        Deque<Integer> stack1=new LinkedList<>();
        Deque<Integer> stack2=new LinkedList<>();

        for(;l1!=null;l1=l1.next) 
            stack1.push(l1.val);
 
        for(;l2!=null;l2=l2.next) 
            stack2.push(l2.val);
        
        ListNode dummyNode =new ListNode(0);

        // ListNode head=null;
        // dummyNode.next= head;
        int advancement=0;
        while(!stack1.isEmpty()||!stack2.isEmpty()){
            int v1=0;
            int v2=0;
            if(!stack1.isEmpty()){
                v1=stack1.pop();
            }
            if(!stack2.isEmpty()){
                v2=stack2.pop();
            }
            int sum=v1+v2+advancement;
            if(sum>=10){
                advancement=1;
            }else{
                advancement=0;
            }
            ListNode temp = new ListNode(sum%10);
            temp.next=dummyNode.next;
            dummyNode.next=temp;
        }
        if(advancement>0){
            ListNode temp = new ListNode(1);
            temp.next=dummyNode.next;
            dummyNode.next=temp;
        }

        return dummyNode.next;
    }
}

赏

谢谢你请我吃糖果

微信