Swift solution - Merge Sort


  • 1
    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
        }
    }
    

  • 0
    Y

    The code looks good! I am trying to write these questions in Swift. Looks like there aren't too many Leetcode swift users.


Log in to reply
 

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