リンクリストの問題をソート

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関数をテストしました。マージも私にはうまく見えます...だからここに何がありますか？

Answer 1

問題はfind_midの機能にあります。 2つのノードのリンクリストでテストすると、最初のノードではなく最後のノードが返されます。

例：だから

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