我得到了两个表示两个非负整数的非空链表。数字以相反的顺序存储,并且每个节点都包含一个数字。任务是将两个数字相加并将其作为链表返回。


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


有几种解决方案。我正在尝试通过将链接列表形成的数字转换为数字来解决此问题。我已经将列表转换为数字,但是我的问题从这里开始。系统会为您提供一个链表定义,并且您不能破坏它。您在此定义中没有默认(空)构造函数。我还不能将我的整数和反转为链表形式。这是我的代码:

public class ListNode {    //given linked -list definition. Should not be manipulated.
     int val;
      ListNode next;
     ListNode(int x) { val = x; }
}

import java.util.*;
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
       int num1 = getNumber(l1);
        int num2 = getNumber(l2);
        int sum = num1 + num2;
        return ??  //some how I should return a LinkedList where my sum is converted into it
    }



//getNumber converts given linked-lists into integers
    public int getNumber(ListNode head) {
       ListNode tmp = head;
    int number = 0;
    int pass = 0;
    while(tmp != null) {
        number += tmp.val * Math.pow(10, pass) ;
        tmp = tmp.next;
        pass++;
    }
    return number;
}

最佳答案

本练习的目的是使用给定的数据结构来执行计算。您不应该将链接列表转换为int。为什么,这些值可能不符合int的限制。使用链接列表,您可以对具有数千位数字的数字执行操作。

这是一个不完整的草图,应该可以帮助您,而又不会破坏练习。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    return addTwoNumbers(l1, l2, 0);
}

private ListNode addTwoNumbers(ListNode l1, ListNode l2, int carry) {
    // TODO: know when to stop!
    // ex: if you have reached the end of l1, then apply carry to l2, if needed, and return
    // ex: if you have reached the end of l2, then apply carry to l1, if needed, and return

    int val = l1.val + l2.val + carry;
    ListNode node = new ListNode(val % 10);
    node.next = addTwoNumbers(l1.next, l2.next, val / 10);
    return node;
}

private ListNode addOne(ListNode l1) {
    // TODO
}

关于java - 将两个数字相加,以反向链接列表形式存储,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/58382465/

10-11 22:34
查看更多