合并排序鏈表-stackoverflow錯誤

我正在嘗試解決 leetcode-148 ( https://leetcode.com/problems/sort-list/ )，即給定 LinkedList 排序，但出現 stackoverflow 錯誤。到目前為止，我已經嘗試過空運行，但沒有看到問題可能發生在哪里.. 遞回的基本條件似乎是正確的，但如果有人看到我沒有看到的東西，我似乎錯過了一些東西..

/**
 * 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.StackOverflowError
  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

uj5u.com熱心網友回復：

有兩個問題：

• 當sortList使用具有 2 個節點的串列呼叫時，然后在第一個回圈（不進行迭代）之后，slow將等于head，并且follow.next = null只會改變在節點之前添加的虛擬head節點。所以本質上鏈表沒有被拆分，遞回呼叫在同一個鏈表上，導致無限遞回。通過更改while條件來解決此問題，以便至少進行一次迭代。此外，您可以在沒有第三個參考 ( follow) 的情況下執行此操作。

• 在merge中，firstandsecond參考不會向前移動，因此回圈將是無限的。

這是更正的代碼：

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

標籤：递归 链表 归并排序

上一篇：如何實作這個程式的遞回版本？

下一篇：使用模運算子獲得圍繞陣列的無限回圈