老哥们能给我看看我这题《链表排序》哪里有问题吗?

# 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节点不见了,这是为什么?


#leetcode##笔试题目##算法工程师#
全部评论
自己顶一下,我学生物的,老哥们帮帮忙,谢了
点赞 回复
分享
发布于 2019-04-18 22:35
把sortlist中间两次出现的sortlist函数放到最后的返回值里面return self.mergr(self.sortlist(head1),self.sortlist(head2))😅😅
点赞 回复
分享
发布于 2019-04-18 23:59
联易融
校招火热招聘中
官网直投

相关推荐

点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务