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; } }
Advertisement
Answer
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;
.