合并2排序链表错误答案

Question

所以我正在做关于合并两个排序链表的hackerrank问题。这就是我的东西

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