Leetcode第2题,出现了检测到循环的错误。

huangapple go评论70阅读模式
英文:

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

我们在这里使用了哨兵节点

参考资料:

  • 有关详细信息,请参阅讨论板,您可以在其中找到许多解释详细的已接受解决方案,涵盖了各种编程语言,包括低复杂度算法和渐近的运行时间/内存分析1, 2
英文:

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

  • For additional details, please see the Discussion Board where you can find plenty of well-explained accepted solutions with a variety of languages including low-complexity algorithms and asymptotic runtime/memory analysis<sup>1, 2</sup>.

huangapple
  • 本文由 发表于 2020年8月26日 18:36:07
  • 转载请务必保留本文链接:https://go.coder-hub.com/63595779.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定