美文网首页
148. Sort List

148. Sort List

作者: April63 | 来源:发表于2018-06-20 10:32 被阅读0次

嗯 stack 的办法很low对不对。

# 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
        """
        stack = []
        while head:
            stack.append(head.val)
            head = head.next
        dummy = ListNode(0)
        p = dummy
        stack.sort()
        while stack:
            p.next = ListNode(stack.pop(0))
            p = p.next
        return dummy.next

阿里当时面试官提示的一种基于二分法的一种办法,类似于快排。。
二分 归并
代码如下:

# 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
        pre = ListNode(0)
        slow = head
        fast = head
        while fast and fast.next:
            pre = slow
            slow = slow.next
            fast = fast.next.next
        pre.next = None
        l1 = self.sortList(head)
        l2 = self.sortList(slow)
        return self.merge(l1, l2)
    def merge(self, l1, l2):
        if not l1:
            return l2
        if not l2:
            return l1
        l = ListNode(0)
        p = l
        while l1 and l2:
            if l1.val < l2.val:
                p.next = l1
                l1 = l1.next
                p = p.next
            else:
                p.next = l2
                l2 = l2.next
                p = p.next
        if l1:
            p.next = l1
        if l2:
            p.next = l2
        return l.next
     

相关文章

  • 2019-01-13

    LeetCode 148. Sort List Description Sort a linked list in...

  • LeetCode #148 2018-07-28

    148. Sort List Sort a linked list in O(n log n) time usin...

  • 链表排序问题

    148. Sort List(链表归并排序)Sort a linked list in O(n log n) ti...

  • 148. Sort List

    嗯 stack 的办法很low对不对。 阿里当时面试官提示的一种基于二分法的一种办法,类似于快排。。二分 归并代码如下:

  • 148. Sort List

    https://leetcode.com/problems/sort-list/description/ Both...

  • 148. Sort List

    Sort a linked list in O(n log n) time using constant spac...

  • 148. Sort List

    题目 Sort a linked list in O(n log n) time using constant s...

  • 148. Sort List

    My Submissions Total Accepted: 90190Total Submissions: 33...

  • 148. Sort List

    这题就是merge sort的链表实现。先看一下mergeSort: 复杂度O(nlogn)。这题的解法我看了ht...

  • 148. Sort List

    Sort a linked list in O(n log n) time using constant spac...

网友评论

      本文标题:148. Sort List

      本文链接:https://www.haomeiwen.com/subject/dxwzeftx.html