如何在Java中迭代地添加链表中的新节点?

Question

我试图从Leetcode这里写一个方法，允许两个排序的链表合并(请忽略我需要添加l2的值更大的情况)。到目前为止，我的策略是创建一个名为mergedList的新链表，并使用while循环迭代地添加新值:

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode temp1 = l1;
ListNode temp2 = l2;
ListNode curr = null;

ListNode mergedList = null;
ListNode testpoint = null;


if(l1 == null && l2 == null) {
return null;
}
else if(l1 == null && l2 != null) {
return l2;
}
else if(l1 != null && l2 == null) {
return l1;
}
else if(l1.next == null && l2.next == null) {
if(l1.val <= l2.val) {
l1.next = new ListNode(l2.val);
return l1;
}
else {
l2.next = new ListNode(l1.val);
return l2;
}
}

if(temp1.val <= temp2.val) {
while(temp1 != null) {
mergedList = new ListNode(temp1.val);
testpoint = mergedList;
while(temp2 != null) {
if(temp1.next != null) {
if(temp1.val <= temp2.val && temp2.val <= temp1.next.val) {
curr = temp2;
mergedList.next = new ListNode(temp2.val);
}
}
temp2 = temp2.next;
}
temp2 = curr;
temp1 = temp1.next;
}
}

System.out.println("");
System.out.println("");

while(testPoint != null) {
System.out.println(testPoint.val);
testPoint = testPoint.next;
}


return mergedList;
}
}

然而，当我尝试打印出mergedList使用testpoint作为指针指向它，唯一的值打印是最后一个值-为什么?我错过了什么，阻止新的链表被正确创建?

Answer 1

一些问题:

• 代码的第二部分创建的所有新节点都被分配给mergedList或mergeList.next，因此以mergeList为首的列表永远不会有超过2个节点。因此，预计您会有只打印一个节点的测试。

• 内部循环用temp1.val创建节点，但是——除了初始情况——从来没有用temp2.val创建节点。

• 嵌套循环很难跟随。使用temp2 = curr;，您将迭代第二个列表几次。这应该是不必要的。

我认为没有必要在代码的第一部分处理这么多基本情况。其中一些可以在更通用的代码的第二部分处理。

也不需要创建temp1和temp2变量。可以使用参数变量l1和l2。

这里有一种方法可以让它工作:

class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode mergedList = null, curr = null, tail = null;
while (l1 != null && l2 != null) { // There are still nodes in both lists
if (l1.val <= l2.val) { // Grab a node from the first list
curr = new ListNode(l1.val);
l1 = l1.next;
} else { // Grab a node from the second list
curr = new ListNode(l2.val);
l2 = l2.next;
}
if (tail == null) {  // First time only
mergedList = curr;
} else {
tail.next = curr;
}
tail = curr; // Keep track of last node in merged list
}
// At least one of the input lists has been processed completely.
// Use the potentially remaining part from the other input list
if (tail == null) { // One input list was empty
return l1 != null ? l1 : l2;
}
tail.next = l1 != null ? l1 : l2;
return mergedList;
}
}

不改变输入列表是一种良好的做法，但是在这种情况下，代码挑战允许这样的改变，因此没有必要创建新的节点:在上面的代码中，您可以替换节点创建部分:

if (l1.val <= l2.val) { // Grab a node from the first list
curr = l1;
l1 = l1.next;
} else { // Grab a node from the second list
curr = l2;
l2 = l2.next;
}