LeetCode-in-All

148. Sort List

Medium

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

Example 1:

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

Output: [1,2,3,4]

Example 2:

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

Output: [-1,0,3,4,5]

Example 3:

Input: head = []

Output: []

Constraints:

• The number of nodes in the list is in the range [0, 5 * 104].
• -105 <= Node.val <= 105

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

Solution

; Definition for singly-linked list:
#|

; val : integer?
; next : (or/c list-node? #f)
(struct list-node
  (val next) #:mutable #:transparent)

; constructor
(define (make-list-node [val 0])
  (list-node val #f))

|#

; Helper function to split the list into two halves
(define (split-list head)
  (let loop ([slow head]
             [fast head]
             [pre #f])
    (cond
      [(or (not fast) (not (list-node-next fast)))
       (when pre
         (set-list-node-next! pre #f))
       slow]
      [else
       (loop (list-node-next slow)
             (list-node-next (list-node-next fast))
             slow)])))

; Helper function to merge two sorted lists
(define (merge-lists l1 l2)
  (let ([dummy (list-node 1 #f)])
    (let loop ([curr dummy]
               [first l1]
               [second l2])
      (cond
        [(not first)
         (set-list-node-next! curr second)]
        [(not second)
         (set-list-node-next! curr first)]
        [else
         (if (<= (list-node-val first) (list-node-val second))
             (begin
               (set-list-node-next! curr first)
               (loop first (list-node-next first) second))
             (begin
               (set-list-node-next! curr second)
               (loop second first (list-node-next second))))])
      (list-node-next dummy))))

; Main sort-list function with contract
(define/contract (sort-list head)
  (-> (or/c list-node? #f) (or/c list-node? #f))
  (cond
    [(or (not head) (not (list-node-next head)))
     head]
    [else
     (let* ([middle (split-list head)]
            [first (sort-list head)]
            [second (sort-list middle)])
       (merge-lists first second))]))

This site is open source. Improve this page.