Leetcode #2, getting detected a cycle error

Tags: , ,



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;
  }
}

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;.



Source: stackoverflow