Leetcode #2，检测到循环错误

Question

我正在尝试解决 leetcode#2，给你两个非空链表，代表两个非负整数。这些数字以相反的顺序存储，并且它们的每个节点都包含一个数字。将这两个数字相加 return 作为一个链表。

您可以假设这两个数字不包含任何前导零，数字 0 本身除外。 https://leetcode.com/problems/add-two-numbers/ 我收到错误：仅针对单个数字的加法检测到循环。我做错了什么？

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 1

在您的代码片段中有几行：

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; 之后以自身的循环边结束。

Answer 2

似乎有些多余的提示和检查。因为它们的顺序相反，所以这是求和的自然顺序。我认为我的代码可以自我解释，但如果您有任何疑问，请告诉我。

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

Answer 3

您遇到的错误似乎已经在已接受的答案中找到，但我们可以稍微简化我们解决此问题的语句，使其更具可读性和更容易理解，如果您愿意：

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

我们在这里使用 Sentinel Node。

参考资料

有关更多详细信息，请参阅 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^{1, 2}。

Leetcode #2，检测到循环错误

Leetcode #2, getting detected a cycle error

java

linked-list

singly-linked-list

参考资料