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. 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;
}
}
3 Answers
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;.
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;
}
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
