Leetcode#2，检测到一个循环错误

Question

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

您可以假设这两个数字不包含任何前导零，除了数字0本身。https://leetcode.com/problems/add-two-numbers/我得到错误：周期检测只为一个数字的加法。我做错了什么？

class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode newpointer = null,
mover = null;
ListNode p = l1,
q = l2;
int carry = 0;
while (p != null || q != null) {
int x = (p == null) ? 0 : p.val;
int y = (q == null) ? 0 : q.val;
int sum = carry + x + y;
carry = sum / 10;
int digit = sum % 10;
ListNode newnode = new ListNode();
newnode.val = digit;
newnode.next = null;
if (newpointer == null) {
newpointer = newnode;
mover = newpointer;
}
mover.next = newnode;
mover = mover.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
if (carry > 0) {
mover.next = new ListNode(carry);
}
return newpointer;
}
}

Answer 1

在代码片段中有几行：

ListNode newnode = new ListNode();
...
if (newpointer == null) {
newpointer = newnode;
mover = newpointer;
}
mover.next = newnode;

这使得LC周期检测算法备受争议。

如果考虑第一次运行while循环，可以发现mover指向与newnode相同的对象。

换句话说，对象ListNode newnode = new ListNode();最终在mover.next = newnode;之后具有其自身的循环边。

Answer 2

似乎有一些多余的指针和检查。因为它们的顺序相反，所以这是求和的自然顺序。我认为我的代码可以自行解释，但如果您有问题，请告诉我。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = null;
ListNode prev = null;
int carry = 0;
while (l1 != null && l2 != null) {
final int sum = l1.val + l2.val + carry;
ListNode cur = new ListNode(sum % 10);
carry = sum / 10;
if (head == null) {
head = cur;
} else {
prev.next = cur;
}
l1 = l1.next;
l2 = l2.next;
prev = cur;
}
ListNode remaining = l1 == null ? l2 : l1;
while (remaining != null) {
int sum = remaining.val + carry;
ListNode cur = new ListNode(sum % 10);
carry = sum / 10;
prev.next = cur;
remaining = remaining.next;
prev = cur;
}
if (carry > 0) {
prev.next = new ListNode(carry);
}
return head;
}

Answer 3

您遇到的错误似乎已经在公认的答案中找到了，但如果您愿意，我们可以稍微简化我们解决这个问题的语句，使其更可读、更容易理解：

public final class Solution {
public static final ListNode addTwoNumbers(
ListNode l1,
ListNode l2
) {
int carry = 0;
final ListNode sentinel = new ListNode(0);
ListNode tail = sentinel;
while (!(l1 == null && l2 == null && carry == 0)) {
final int add1 = l1 != null ? l1.val : 0;
final int add2 = l2 != null ? l2.val : 0;
final int sum = add1 + add2 + carry;
carry = 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