英文:
Leetcode #2, getting detected a cycle error
问题
我正在尝试解决LeetCode问题#2,给你两个非空链表,表示两个非负整数。这些数字以相反的顺序存储,每个节点包含一个个位数。将这两个数字相加,并将其作为一个链表返回。
你可以假设这两个数字除了数字0本身外,不会包含任何前导零。
问题链接
我遇到了错误:仅对于相加为个位数的数字出现循环。我做错了什么?
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;
}
}
英文:
I was trying to solve leetcode#2, You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
https://leetcode.com/problems/add-two-numbers/
I am getting Error: cycle detected only for additon of single digit numbers.
What am I doing wrong?
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;
}
}
答案1
得分: 3
在你的代码片段中有以下几行:
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;
之后形成了一个指向自身的循环边。
英文:
In your code snippet there are lines:
ListNode newnode = new ListNode();
...
if (newpointer == null) {
newpointer = newnode;
mover = newpointer;
}
mover.next = newnode;
It makes the LC cycle detection algorithm complain.
If you consider the first run of the while
loop, you can find that mover
points to the same object to which newnode
does.
In other words, object ListNode newnode = new ListNode();
ends up with a cyclic edge to itself after mover.next = newnode;
.
答案2
得分: 0
以下是翻译好的内容:
似乎有一些冗余的指针和检查。由于它们是以相反的顺序,这是求和的自然顺序。我认为我的代码已经解释了自身,但如果你有问题,请让我知道。
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;
}
英文:
There seems to be some redundant pointers and checks. Because they are in reversed order it is the natural order of summation. I think my code explains itself but if you have questions let me know.
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;
}
答案3
得分: 0
以下是翻译好的部分:
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;
}
}
我们在这里使用了哨兵节点。
参考资料:
英文:
The bug you were getting seems to be already found in the accepted answer, yet we can just a bit simplify our statements for solving this problem to be more readable and easier to understand, if you will:
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;
}
}
We are using a Sentinel Node here.
References
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论