“This is the 29th day of my participation in the Gwen Challenge in November. See details of the event: The Last Gwen Challenge in 2021”

describe

Given the head of a linked list, return the list after sorting it in ascending order.Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]
Copy the code

Example 2:

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
Copy the code

Example 3:

Input: head = []
Output: []
Copy the code

Note:

The number of nodes in the list is in the range [0, 5 * 10^4].
-10^5 <= Node.val <= 10^5
Copy the code

parsing

The first node of a linked list is called head. They also want us to use O(n logn) time complexity and O(1) memory. I tried the simplest violent insertion, order one in space, but order n^2 in time, I still timed out.

answer

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:return head
        L = ListNode(val=-1000000)
        L.next  = cur = head
        while cur.next:
            pre = L
            if cur.next.val >= cur.val:
                cur = cur.next
                continue
            while pre.next.val < cur.next.val:
                pre = pre.next
            tmp  = cur.next
            cur.next = tmp.next
            tmp.next = pre.next
            pre.next = tmp
        return L.next

        	      
		
Copy the code

The results

Time Limit Exceeded
Copy the code

parsing

Because the built-in function sorted is used to sort the values and rebuild the linked list, the time complexity is O(n logn), but it passes the shame. But the space complexity is order n.

answer

class ListNode(object): def __init__(self, val=0, next=None): self.val = val self.next = next class Solution(object): def sortList(self, head): """ :type head: ListNode :rtype: ListNode """ if not head or not head.next: return head node = ListNode(val = 0) result = node nlist = [] while head ! = None: nlist.append(head.val) head = head.next nlist = sorted(nlist) for n in nlist: node.next = ListNode(val = n) node = node.next return result.nextCopy the code

The results

Given in the Python online submission List. Memory Usage: 10000 ms Given in the Python online submissions for Sort List.Copy the code

parsing

You can use merge sort, as long as it’s order n logn.

answer

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:return head
        mid = self.getMid(head)
        another = mid.next
        mid.next = None
        return self.merge(self.sortList(head), self.sortList(another))
    
    def getMid(self, head):
        fast = slow = head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        return slow
    
    def merge(self, A, B):
        dummy = cur = ListNode(0)
        while A and B:
            if A.val > B.val:
                cur.next = B
                B = B.next
            else:
                cur.next = A
                A = A.next
            cur = cur.next
        if A: cur.next = A
        if B: cur.next = B
        return dummy.next
        
        
        
 
Copy the code

The results

Given in the Python online submission List. Memory Usage: 10000 ms Submissions in Python online submissions for Sort List.Copy the code

Original link: leetcode.com/problems/so…

Your support is my biggest motivation