将链表保存在leetcode中的java中，添加两个数字

Question

我正在Leetcode上解决这个问题。然而，我有一个问题，返回墨迹列表。

您会得到两个非空链表，表示两个非负整数。这些数字以相反的顺序存储，并且它们的每个节点都包含一个数字。将这两个数字相加，并将其作为链表返回。

您可以假设这两个数字不包含任何前导零，除了数字0本身。

示例：

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
# Singly Linked List  #

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/

问题

在代码的最后部分，我意识到我无法将插入的数字保存在head中。我注意到head.next=新ListNode(sum%10(；`正在覆盖我的节点。如何保存列表的状态？

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
StringBuilder a = new StringBuilder();
StringBuilder b = new StringBuilder();

ListNode temp = l1;
ListNode temp2 = l2;
while(temp != null || temp2 != null) {
a.append(temp.val);
b.append(temp2.val);
temp = temp.next;
temp2 = temp2.next;
}
int sum =  Integer.parseInt(a.reverse().toString()) +                                                     Integer.parseInt(b.reverse().toString());

ListNode head = new ListNode(0); 

while(sum != 0) {
head.next = new ListNode(sum % 10);
head = head.next;
sum /= 10;
}

return head;
}

Answer 1

我们会使用一个sentinel节点(就在head或启动节点之前(来解决这个问题。然后，我们只使用return sentinel.next;而不是return head;。

这将通过：

public final class Solution {
public static final ListNode addTwoNumbers(
ListNode l1, 
ListNode l2
) {
int left = 0;
ListNode sentinel = new ListNode(0);
ListNode tail = sentinel;
while (!(l1 == null && l2 == null && left == 0)) {
final int add1 = l1 != null ? l1.val : 0;
final int add2 = l2 != null ? l2.val : 0;
final int sum = add1 + add2 + left;
left = sum / 10;
final ListNode tempNode = new ListNode(sum % 10);
tail.next = tempNode;
tail = tempNode;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
return sentinel.next;
}
}

---

参考文献

• 有关更多详细信息，请参阅讨论板，您可以在其中找到大量解释良好的公认解决方案，使用各种语言，包括高效算法和渐近时间/空间复杂性分析^1，2

Answer 2

为什么不在迭代l1和l2的同时构建结果列表？我们不需要StringBuilder、parseInt或reverse()。

运行时间：1毫秒，比1100.00%的Java在线提交的AddTwo Numbers快。内存使用率：39.6 MB，低于75.33%的Java在线提交的AddTwo Numbers。

这是我的解决方案

class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode res = new ListNode(0);
ListNode ret = res;
int carry = 0;
while (l1 != null || l2 != null) {
int a = l1 == null ? 0 : l1.val;
int b = l2 == null ? 0 : l2.val;
l1 = l1 == null ? null : l1.next;
l2 = l2 == null ? null : l2.next;
res.next = new ListNode((a + b + carry) % 10);
res = res.next;
carry = ((a + b + carry) / 10);
}
if (carry != 0) res.next = new ListNode(carry);
return ret.next;
}

}

Answer 3

问题是由head = head.next;行引起的。这会覆盖变量头，这就是为什么程序总是返回"最后一个"节点的原因。解决方案是返回一个不同的变量。然而，还有另一个问题。也就是说，您返回的列表总是尾随0。例如，对于您给出的示例imput，它返回0->7->0->8.这是因为您总是将列表初始化为0。这里有一个可能的(不那么优雅，但很快(解决方案。

编辑

为了防止不同大小的列表出现NullPointerException，字符串的生成被放入一个方法中，每个列表调用一次。增加了对空节点情况的管理

EDIT 2添加了功能的重新生成和空节点情况的管理

public String nodeToString(ListNode l){
StringBuilder a = new StringBuilder();
ListNode temp = l;
while(temp != null ) {
a.append(temp.val);
temp = temp.next;

}
return a.reverse().toString();
}
public Integer nodeToInt(ListNode l){
String a=nodeToString(l);
Integer ret=0;
if(a.length()>0)
ret=Integer.parseInt(a);
return ret;
}

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {


Integer a=nodeToInt(l1);
Integer b=nodeToInt(l2);
int sum =  a+b;   
ListNode head = new ListNode(sum % 10); 
sum /= 10;

ListNode retVal=head;

while(sum != 0) {
head.next = new ListNode(sum % 10);
head = head.next;
sum /= 10;
}

return retVal;
}