Swift solution - Merge Sort


  • 0
    class Solution {
        func sortList(_ head: ListNode?) -> ListNode? {
            if head == nil || head?.next == nil {
                return head
            }
            
            var pre: ListNode? = nil
            var slow: ListNode? = head
            var fast: ListNode? = head
            
            while fast != nil && fast?.next != nil {
                pre = slow
                slow = slow?.next
                fast = fast?.next?.next
            }
            pre?.next = nil
            let l1 = sortList(head)
            let l2 = sortList(slow)
            
            return merge(l1, l2)
        }
        
        private func merge(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
            let dummy = ListNode(0)
            var l1 = l1
            var l2 = l2
            var cur: ListNode? = dummy
            
            while l1 != nil && l2 != nil {
                if l1!.val < l2!.val {
                    cur?.next = l1
                    l1 = l1?.next
                } else {
                    cur?.next = l2
                    l2 = l2?.next
                }
                cur = cur?.next
            }
            if l1 != nil {
                cur?.next = l1
            }
            if l2 != nil {
                cur?.next = l2
            }
            
            return dummy.next
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.