合并 2 个排序链表错误答案

Question

所以我正在合并两个排序的链表时解决黑客排名问题。这就是我所拥有的

// Complete the mergeLists function below.
/*
* For your reference:
*
* SinglyLinkedListNode {
*     int data;
*     SinglyLinkedListNode next;
* }
*
*/
static SinglyLinkedListNode mergeLists(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
SinglyLinkedListNode curr1 = head1;
SinglyLinkedListNode curr2 = head2;
SinglyLinkedListNode head = new SinglyLinkedListNode(0);
SinglyLinkedListNode curr = head;

while(curr1.next != null && curr2.next != null){
if(curr1.data < curr2.data ){
curr.next = curr1;
curr = curr.next;
curr1 = curr1.next;

}
else{
curr.next = curr2;
curr=curr.next;
curr2 = curr2.next;
}
}
if (curr1.next == null ){
curr.next = curr2;
}

head = head.next;
return head;

}
private static final Scanner scanner = new Scanner(System.in);

但是这是我得到的输出

1 2 3 4 而不是

1 2 3 3 4

测试用例是

链表 1 ： 1,2,3 链表2：3,4

Answer 1

当两个元素彼此相等时，您缺少if子句。

else if (curr1.data > curr2.data) {
curr.next = curr2;
curr = curr.next;
curr2 = curr2.next;
} else {
// assign node from 2nd list
curr.next = curr2;
// increment 2nd list
curr2 = curr2.next;
curr = curr.next;
// asign node from 1st list
curr.next = curr1;
// increment 1st list
curr1 = curr1.next;
curr = curr.next;
} 

Answer 2

当其中一个完成时，您需要将头分配给剩余的列表。在两个列表大小不同的情况下会发生这种情况：

取代

if (curr1.next == null ){
curr.next = curr2;
}

跟

if (curr1.next == null ){
curr.next = curr2;
} else if (curr2.next == null ){
curr.next = curr1;
}