使用java合并排序链表

Question

private static void mergeSort(Node<Integer> head) {
    if (head==null || head.next == null) {
        return;
    }

    Node<Integer> temp1 = head;
    Node<Integer> temp2 = head;
    int count = 0;
    while (temp2 != null && temp2.next != null) {
        temp1 = temp1.next;
        temp2 = temp2.next.next;
        count++;
    }
    Node<Integer> list1 = head;
    Node<Integer> listTemp1 = list1;
    while (count > 0) {
        listTemp1 = listTemp1.next;
        count--;
    }
    Node<Integer> list2 = listTemp1.next;
    listTemp1.next = null;

    mergeSort(list1);
    mergeSort(list2);

    Node<Integer> finalHead = null;
    Node<Integer> finalTail = null;
    if (list1.data < list2.data) {
        finalHead = list1;
        list1 = list1.next;
    } else {
        finalHead = list2;
        list2 = list2.next;
    }
    finalTail = finalHead;

    while (list1 != null && list2 != null) {
        if (list1.data < list2.data) {
            finalTail.next = list1;
            finalTail = list1;
            list1 = list1.next;
        } else {
            finalTail.next = list2;
            finalTail = list2;
            list2 = list2.next;
        }
    }

    if (list1 == null) {
        finalTail.next = list2;
    } else if (list2 == null) {
        finalTail.next = list1;
    }

    return;

}

它抛出堆栈溢出错误。请帮助我纠正我的解决方案，我首先将我的链表分成两半，然后递归地发送它们，之后我将合并我的两个排序链表。当我递归调用我的第一个列表时，显示错误

Answer 1

如果你有一个包含2个元素的列表，那么它会递归地调用这个方法：

   while (temp2 != null && temp2.next != null) {
        temp1 = temp1.next;
        temp2 = temp2.next.next;
        count++;
    }

计数将等于"1“

   Node<Integer> list1 = head;
    Node<Integer> listTemp1 = list1;
    while (count > 0) {
        listTemp1 = listTemp1.next;
        count--;
    }

listTemp1将指向第二个节点

   Node<Integer> list2 = listTemp1.next;
    listTemp1.next = null;
    mergeSort(list1);
    mergeSort(list2);

因此，从我看到的情况来看，list1将继续指向第一个节点，list2将继续指向null，请注意，listTemp1.nex = null实际上什么也不做，因为它已经指向了null

您可以通过减少计数来简单地解决这个问题。