排序排序链表链表问题

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