链表实现未形成链接（Java）

Question

我正在尝试解决一道Leetcode问题，需要在Java中实现一个链表，但是“链接”从未被创建。节点本身确实被创建了，但在内存中丢失了。我知道如何使用指针在C++中完成这个任务，但在Java中该如何实现呢？

问题：

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

输出：

7
0
8

返回：

7 (just head node)

我的代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        //hold root node to return later, use temp node (l3) to create list
        ListNode head = new ListNode(0);
        ListNode l3 = head;

        boolean carryover = false;

        //if lists l1, l2 still have a value, append to l3
        while (l1 != null || l2 != null)
        {
            //always true except on first iteration
            if (l3 == null)
                l3 = new ListNode(0);

            //if l1.val + l2.val >= 10 from last iteration, carry over 1
            if (carryover)
            {
                l3.val += 1;
                carryover = false;
            }

            if (l1 != null)
            {
                l3.val += l1.val;
                l1 = l1.next;
            }

            if (l2 != null)
            {
                l3.val += l2.val;
                l2 = l2.next;
            }

            if (l3.val > 9)
            {
                l3.val -= 10;
                carryover = true;
            }
            System.out.println(l3.val);

            //create next 'link' in list
            l3 = l3.next;
        }
        return head;
    }
}

- Gyn Manstot

---

通常每个Node都有一个变量，称为next。 next变量的类型是Node。如果您想将新节点添加到列表中，则该方法会创建一个新的Node并使用先前的tail来tail.next = myNewNode;，然后更新tail，如tail = myNewNode;。只需在Google上搜索“LinkedList”Java实现，就会有很多示例。 - Zabuzard

在Java中，您可以像在C或C ++中使用结构体一样使用类。 - Shubham Agarwal Bhewanewala

哈哈，我上周五已经回答了这个确切的问题。 - Michael

Answer 1

合并两个列表，每个列表由第一个节点（头）定义

private Node merge(Node list1, Node list2){
    if (list1.next == null && list2.next == null)
        return new Node(0);
    else if (list1.next == null)
        return list2;
    else if (list2.next == null)
        return list1;
    else {
        Node curr = list1.next;
        while (curr.next != null){
            curr = curr.next;
        }
        curr.next = list2.next;
        return list1;
    }
}

- shahaf

Answer 2

l3 = l3.next; 并不是你想象中的那样。

当 l3.next 是 null 时，你将把 null 赋值给 l3。这个 null 不是内存中由 l3.next 指向的一个特殊位置，它只是简单的 null，也就是说它没有指向任何东西。

所以在下一个循环中，当你执行 l3 = new ListNode(0); 时，你只是创建了一个断开的节点。

你应该先确保 next 正确地指向一个节点，然后再对它进行操作。

因此，你可以尝试这样做：

boolean first = true;

//if lists l1, l2 still have a value, append to l3
while (l1 != null || l2 != null)
{
    // create the next node
    if (!first) {
        // create the next node and attach it to the current node
        l3.next = new ListNode(0);
        // we now work with the next node
        l3 = l3.next;
    } else {
        first = false;
    }

    //if l1.val + l2.val >= 10 from last iteration, carry over 1
    if (carryover)
    {
        l3.val += 1;
        carryover = false;
    }

    if (l1 != null)
    {
        l3.val += l1.val;
        l1 = l1.next;
    }

    if (l2 != null)
    {
        l3.val += l2.val;
        l2 = l2.next;
    }

    if (l3.val > 9)
    {
        l3.val -= 10;
        carryover = true;
    }
    System.out.println(l3.val);

}

- Loris Securo