单链表的排序

单链表的排序_牛客题霸_牛客网

问题简述

给定一个节点数为n的无序单链表，对其按升序排序。

思路1：归并排序

• 细节：

  • 找中点的时候，定位到中点的前一个位置，保存中点位置后切断，否则会无限循环；

  • 递归的 base case：最好判断为空节点或只有一个节点时就返回；

Python

class Solution:
    def sortInList(self , head: ListNode) -> ListNode:
        
        def merge(h):
            if not h or not h.next: return h
            
            # 找中点
            f, s = h.next, h
            while f and f.next:
                f = f.next.next
                s = s.next
            
            # 切断
            m, s.next = s.next, None
            l, r = merge(h), merge(m)
            
            # 合并
            cur = dummy = ListNode(0)
            while l and r:
                if l.val < r.val:
                    cur.next = l
                    l = l.next
                else:
                    cur.next = r
                    r = r.next
                cur = cur.next
            
            cur.next = l if l else r
            return dummy.next
        
        return merge(head)

思路2：快排（超时）

• 链表的快排比数组好写一点，因为链表可以方便的移动节点，而不需要要交换；

• 默认使用头结点作为 pivot，因此部分用例无法通过（超过最大递归）；

• 对链表来说似乎没有很好的办法来确定 pivot；

Python

class Solution:
    def sortInList(self , head: ListNode) -> ListNode:
        
        import sys
        sys.setrecursionlimit(1000000)
        
        def qsort(h):
            if not h or not h.next: return h
            
            s = small = ListNode(0)
            l = large = ListNode(0)
            cur = h.next
            while cur:
                if cur.val <= h.val:
                    s.next = cur
                    s = s.next
                else:
                    l.next = cur
                    l = l.next
                cur = cur.next
            
            s.next = h
            h.next = l.next = None
            
            small = qsort(small.next)
            large = qsort(large.next)
            h.next = large
            
            return small
        
        ret = qsort(head)
        return ret