排序排序鏈表鏈表問題

Question

我的代碼如下：

def sort_list(head) 
    return head if head.nil? || head.next.nil? 
    mid_node = find_mid(head) 
    second_half = mid_node.next 
    mid_node.next = nil 
    left_half = sort_list(head) 
    right_half = sort_list(second_half) 

    merge(left_half, right_half) 

end 

def merge(left_head, right_head) 

    left = left_head 
    right = right_head 
    dummy_head = dummy = ListNode.new(-1) 


    until left.nil? || right.nil? 
     if left.val > right.val 
      dummy.next = right 
      right = right.next 
     else 
      dummy.next = left 
      left = left.next 
     end 
     dummy = dummy.next 
    end 

    #here there may be one list left over. 
    dummy.next = left unless left.nil? 
    dummy.next = right unless right.nil? 

    dummy_head.next 
end 

def find_mid(head) 
    return nil if head.nil? 

    slow_ptr = fast_ptr = head 
    until fast_ptr.nil? || fast_ptr.next.nil? 
     fast_ptr = fast_ptr.next.next 
     slow_ptr = slow_ptr.next 
    end 

    slow_ptr 
end 

這是給我一個堆棧太深的錯誤，我不知道爲什麼。好像我正在終止這兩個功能。 sort_list邏輯對我來說看起來很好，我測試了find_mid函數。 Merge對我來說也很好......所以這裏有什麼？

Answer 1

問題出在您的find_mid函數。如果你用一個只有兩個節點的鏈表來測試它，你會看到它返回的是最後一個，而不是第一個。

例子：

list = ListNode.new(4, ListNode.new(3)) 
res = find_mid(list) 
puts res.val # It would print 3 

因此，列表不會收縮任何更多的代碼會重複遞歸大小爲2 永遠，還是在現實的鏈表，直到堆棧太深度錯誤。

然後在溶液中改變功能如下：

def find_mid(head) 
    return nil if head.nil? 

    slow_ptr = head 
    fast_ptr = head.next 
    until fast_ptr.nil? || fast_ptr.next.nil? 
     fast_ptr = fast_ptr.next.next 
     slow_ptr = slow_ptr.next 
    end 

    slow_ptr 
end