java - 合并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

标签： javamergelinked-list

Answer 1

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

代替

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

和

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