老哥们能给我看看我这题《链表排序》哪里有问题吗?
# Definition for singly-linked list. class ListNode(object): def __init__(self, x): self.val = x self.next = None class Solution(object): def sortList(self, head): """ :type head: ListNode :rtype: ListNode """ if not head or not head.next: return head head1 = head head2 = self.split(head) self.sortList(head1) self.sortList(head2) return self.merge(head1, head2) def split(self, head): if not head: return head slow, fast = head, head while fast.next and fast.next.next: slow = slow.next fast = fast.next.next head2 = slow.next slow.next = None return head2 def merge(self, head1, head2): if not head1: return head2 if not head2: return head1 dummy = ListNode(73) p = dummy while head1 and head2: if head1.val <= head2.val: p.next = head1 head1 = head1.next else: p.next = head2 head2 = head2.next p = p.next if head1: p.next = head1 if head2: p.next = head2 return dummy.next a = [4 , 2, 1, 3] def build_list(nums): if not nums: return None cur_node = ListNode(nums[0]) cur_node.next = build_list(nums[1:]) return cur_node b = build_list(a) c = Solution() d = c.sortList(b)
是leetcode上的一个题,把一个链表排序,我看了半天也没看出问题。
在http://www.pythontutor.com/visualize.html#mode=edit 可视化尝试debug下,在某一步return时直接把我一个节点吃了,可我明明没有返回错值。
请大佬们抽个一分钟看看,谢谢了。可视化图在这儿:第一个图当前函数返回前, 第二个图是当前函数返回后,我的2节点不见了,这是为什么?