May 10, 2021

Leetcode 148 Sort List

Given the head of a linked list, return the list after sorting it in ascending order.






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





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

Input: head = []
Output: []

Soruda bizden karışık olarak verilen linked listi küçükten büyüğe doğru sıralamamız isteniyor.
Bunun için mergesort sıralamasını kullanabiliriz.T.C. nlogn dir.
Mergesort için linkedlist ortadan ikiye bölüp iki yeni liste oluştururuz.Ve bu listeleri kendi içinde tekrar küçükten büyüğe sıralarız.
Yani rekürsif olarak sortList fonksiyonunu tekrar ,tekrar çağırırız.
Son olarakta merge fonksiyonu ile bölünmüş listeleri birleştiririz.

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        
        #listeyi ikiye bölelim
        left = head
        right = self.getMid(head)
        tmp = right.next
        right.next = None
        right = tmp
        
        left = self.sortList(left)
        right = self.sortList(right)
        return self.merge(left,right)
    
    def getMid(self,head):
        slow,fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow
    
    def merge(self,list1,list2):
        tail = dummy = ListNode()
        while list1 and list2:
            if list1.val<list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next
            tail = tail.next
        if list1:
            tail.next = list1
        if list2:
            tail.next = list2
        return dummy.next