（python) leetcode刷题——sort-list

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

解析：
对单链表进行时间复杂度为O(nlogn)，空间复杂度为O(1)的排序算法
单链表的归并排序时间复杂度为O(nlogn)，由于结构特殊性，只需要一个辅助的节点，空间复杂度恒定。
下面作图演示算法过程：
1，输入：【3，4，2，1】
（python) leetcode刷题——sort-list
2，递归找到链表中点mid并进行拆分：

3，对每次左右分别排序，引用辅助结点pre，并归并起来：

代码：
找到中点并拆分操作：

def sort(arr):
    if arr is None or arr.next is None:
        return arr
    pre = arr
    mid = arr
    lon = arr
    while lon and lon.next:
        pre = mid
        mid = mid.next
        lon = lon.next.next
    left,right = arr,mid
    pre.next = None
    return sortlink(sort(left),sort(right))

归并操作：

def sortlink(left,right):
    pre = node(-1)
    first = pre
    while left and right:
        if left.val > right.val:
            pre.next = right
            pre = right
            right = right.next
        else:
            pre.next = left
            pre = left
            left = left.next
    if left:
        pre.next = left
    else:
        pre.next = right
    return first.next

全部代码：

class node(object):
    def __init__(self,val,p = None):
        self.val = val
        self.next = p

def Linklist(a):
    for i in range(len(a)):
        a[i] = node(a[i])
    for i in range(len(a)-1):
        a[i].next = a[i+1]    
    return a

def sort(arr):
    if arr is None or arr.next is None:
        return arr
    pre = arr
    mid = arr
    lon = arr
    while lon and lon.next:
        pre = mid
        mid = mid.next
        lon = lon.next.next
    left,right = arr,mid
    pre.next = None
    return sortlink(sort(left),sort(right))   

 def sortlink(left,right):
    pre = node(-1)
    first = pre
    while left and right:
        if left.val > right.val:
            pre.next = right
            pre = right
            right = right.next
        else:
            pre.next = left
            pre = left
            left = left.next
    if left:
        pre.next = left
    else:
        pre.next = right
    return first.next

if __name__=='__main__':
    a = [3,4,2,1]
    Link = Linklist(a)
    s = Link[0]
    print('排序前：')
    while s:
        print(s.val)
        s = s.next 
    b = sort(Link[0])
    print('排序后：')
    while b:
        print(b.val)
        b = b.next

（python) leetcode刷题——sort-list

相关推荐