讨论/算法和数据结构/求两个正整数的和,数据结构为链表(Java语言)/
求两个正整数的和,数据结构为链表(Java语言)

求两个正整数的和,数据结构为链表,不允许改变数据结构。

1->2->3->4
      3->4
输出
1->2->6->8

有人知道怎么做么?仅限 Java 语言,本人只看得懂 Java,谢谢啦!

展开讨论
共 4 个讨论

有一个容易理解的思路:(反转、反转、ok了)
1.反转两个链表;
2.将两个链表的值相加变为链表;
3.将相加的链表反转。

3

两个链表各遍历一遍,分别求出1234和34,求和1268,然后将1268转成链表

这是力扣第 445 题:两数相加 II,不能反转链表的话,就得借助栈完成了。

注意:要考虑进位问题,编码的话可以参考一下其他朋友的代码,很多类似的“不正常”的加法问题编码基本都是一个套路。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> stack1=new Stack<>();
        while (l1!=null){
            stack1.push(l1.val);
            l1=l1.next;
        }
        Stack<Integer> stack2=new Stack<>();
        while (l2!=null){
            stack2.push(l2.val);
            l2=l2.next;
        }
        Stack<Integer> stackans=new Stack<>();
        int temp;
        int upper=0;
        while (!stack1.empty()&&!stack2.empty()){
            temp=stack1.pop()+stack2.pop()+upper;
            upper=temp/10;
            temp=temp%10;
            stackans.push(temp);
        }
        while (!stack1.empty()){
            temp=stack1.pop()+upper;
            upper=temp/10;
            temp=temp%10;
            stackans.push(temp);
        }
        while (!stack2.empty()){
            temp=stack2.pop()+upper;
            upper=temp/10;
            temp=temp%10;
            stackans.push(temp);
        }
        if (upper!=0)stackans.push(upper);
        ListNode root=new ListNode(stackans.pop());
        ListNode templist=root;
        while (!stackans.empty()){
            templist.next=new ListNode(stackans.pop());
            templist=templist.next;
        }
        return root;
        }

不对列表中的节点进行翻转的做法。

原题下面有不少好的做法。