在 Java 中使用归并排序对 LL 进行排序

Question

我正在尝试使用 Java 中的归并排序对链接列表进行排序。但是，我没有将排序的链接列表作为输出。这是代码：-

/**
 * 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 sortList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode middle = findMiddle(head);
        ListNode rightHead = middle.next;
        middle.next = null;
        ListNode leftHead = head;
        leftHead = sortList(leftHead);
        rightHead = sortList(rightHead);

        return merge(leftHead,rightHead);
    }
    public ListNode merge(ListNode leftHead, ListNode rightHead){
        ListNode dummyHead = new ListNode(-1);
        ListNode temp = dummyHead;
        while(leftHead!=null && rightHead!=null){
            if(leftHead.val<rightHead.val){
                temp.next = leftHead;
                temp = leftHead;
                leftHead = leftHead.next;
            }else{
                temp.next = rightHead;
                temp = rightHead;
                rightHead = rightHead.next;
            }
            // temp = temp.next;
        }
        if(leftHead!=null){
            temp.next = new ListNode(leftHead.val);
            leftHead = leftHead.next;
            temp = temp.next;
            }
        else if(rightHead!=null){
            temp.next = new ListNode(rightHead.val);
            rightHead = rightHead.next;
            temp = temp.next;      
        }
        return dummyHead.next;
    }
    public ListNode findMiddle(ListNode head){
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

我使用了标准的归并排序算法，该算法用于对数组进行排序，只是将数据类型更改为链接列表。没有编译器错误，所以我想我的逻辑一定有问题。

Answer 1

将合并中的最后两个 if 更改为 while 应该可以解决问题：

        while(leftHead!=null){
            temp.next = new ListNode(leftHead.val);
            leftHead = leftHead.next;
            temp = temp.next;
        }
        while(rightHead!=null){
            temp.next = new ListNode(rightHead.val);
            rightHead = rightHead.next;
            temp = temp.next;      
        }