【 topic description 】

【 原 文 】

To sort linked lists, there are many ways, because the required time complexity is O(nlogn) space complexity is constant level, so we need to choose among many sorts, to meet the time complexity of the sorting algorithm is quick sort, heap sort, hill sort and merge sort. Because the worst case of fast sorting is order n times n, it doesn’t satisfy, and since it’s a linked list, we can’t use numbers to indicate the position, so we choose merge sort.

Merge sort is to keep finding the midpoint of the current list, split it into two parts, and keep splitting the two parts until there are only two values left in each segment, sort the two values, and then keep returning to the upper sort. Two by two, then four by four, then eight by eight, and finally the whole list is sorted.

First write a linked list to find the function of the midpoint, using the method of fast and slow Pointers, fast Pointers and slow Pointers start from the head, the slow pointer goes one step at a time, the fast pointer goes two steps at a time, when the fast pointer goes to his next next is empty, it stops, at this time the slow pointer goes to the middle position. The return value is an intermediate pointer.

def getmid(self,head):# link list fast and slow pointer to find the midpoint
       slow=fast=head
       if head is None :return slow
       while fast.next and fast.next.next:
           slow=slow.next
           fast=fast.next.next
       return slow
Copy the code

Write a sorting function that sorts the two lists and returns the sorted head pointer

def merge(self,l,r):
       a=ListNode(0)
       q=a
       while l and r:
           if l.val>r.val:
               q.next=r
               r=r.next
           else:
               q.next=l
               l=l.next
           q=q.next
       if l:
           q.next=l
       if r:
           q.next=r
       return a.next
Copy the code

In the main function, we recursively call ourselves, and the logic that the main function does is to find the middle pointer, and then we cut the list in two, and we use L for the first one, r for the second one,

 def sortList(self, head):
       """ :type head: ListNode :rtype: ListNode """
       if head is None or head.next is None:return head
       mid=self.getmid(head)
       l=head
       r=mid.next
       mid.next=None
       return self.merge(self.sortList(l),self.sortList(r))
Copy the code

[source code] merge sort

# 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 head is None or head.next is None:return head
        mid=self.getmid(head)
        l=head
        r=mid.next
        mid.next=None
        return self.merge(self.sortList(l),self.sortList(r))
    def getmid(self,head):# link list fast and slow pointer to find the midpoint
        slow=fast=head
        if head is None :return slow
        while fast.next and fast.next.next:
            slow=slow.next
            fast=fast.next.next
        return slow
    def merge(self,l,r):
        a=ListNode(0)
        q=a
        while l and r:
            if l.val>r.val:
                q.next=r
                r=r.next
            else:
                q.next=l
                l=l.next
            q=q.next
        if l:
            q.next=l
        if r:
            q.next=r
        return a.next
Copy the code