合并排序链表 - 堆栈溢出错误

Question

我正在尝试解决 leetcode-148 (https://leetcode.com/problems/sort-list/)，即对给定的 LinkedList 进行排序，但出现了计算器溢出错误。到目前为止，我已经尝试过 dry 运行但我没有看到问题可能发生的地方。递归的基本条件似乎是正确的，但如果有人看到我没有看到的东西，我似乎错过了一些东西..

/**
 * 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 follow = new ListNode(0);
        follow.next=head;
        ListNode fast = head;
        ListNode slow = head;
        
        // Find the mid-point of the list
        while (fast.next!=null && fast.next.next!=null) {
            slow=slow.next;
            fast=fast.next.next;
            follow=follow.next;
        }

        // Split the list
        follow.next = null;
        
        // Sort each half
        ListNode first = sortList(head);
        ListNode second = sortList(slow);
        
        // Merge
        return merge(first, second);
    }
    
    private ListNode merge(ListNode first, ListNode second) {
        if (first==null) return second;
        if (second==null) return first;
        
        ListNode result = new ListNode(0);
        ListNode head = result;
        
        while (first!=null && second!=null) {
            if (first.val<second.val) {
                result.next = first;
            } else {
                result.next = second;
            }
            
            result=result.next;
        }
        
        if (first!=null) {
            result.next = first;
            result=result.next;
        }
        
        if (second!=null) {
            result.next = second;
            result=result.next;
        }
        
        return head.next;
    }
}

这是错误

WARNING: A command line option has enabled the Security Manager
WARNING: The Security Manager is deprecated and will be removed in a future release
java.lang.WhosebugError
  at line 31, Solution.sortList
  at line 31, Solution.sortList
  at line 31, Solution.sortList
  at line 31, Solution.sortList
  at line 31, Solution.sortList

Answer 1

有两个问题：

当使用具有 2 个节点的列表调用 sortList 时，在第一个循环（不进行迭代）之后，slow 将等于 head，而 follow.next = null 只会改变在 head 节点之前添加的虚拟节点。所以本质上链表没有拆分，递归调用在 same 列表上，导致无限递归。通过更改 while 条件来解决此问题，以便至少进行一次迭代。此外，您可以在没有第三个参考的情况下执行此操作 (follow)。
在merge中，first和second引用不向前，所以会无限循环。

这里是更正后的代码：

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;

    ListNode fast = head.next;
    ListNode slow = head;
    
    // Find the mid-point of the list
    while (fast != null && fast.next != null) { // iterate at least once
        slow = slow.next;
        fast = fast.next.next;
    }

    // Split the list
    ListNode second = slow.next;
    slow.next = null;
    
    // Sort each half
    head = sortList(head);
    second = sortList(second);
    
    // Merge
    return merge(head, second);
}

private ListNode merge(ListNode first, ListNode second) {
    ListNode result = new ListNode(0);
    ListNode head = result;
    
    while (first != null && second != null) {
        if (first.val < second.val) {
            result.next = first;
            first = first.next; // move forward
        } else {
            result.next = second;
            second = second.next;
        }            
        result = result.next;
    }
    if (first != null) {
        result.next = first;
        result = result.next;
    }
    if (second != null) {
        result.next = second;
        result = result.next;
    }
    return head.next;
}

合并排序链表 - 堆栈溢出错误

merge sort linkedlist - stackoverflow error

recursion

mergesort

linked-list