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:

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

Solution

import com_github_leetcode.ListNode

/*
 * Definition for singly-linked list.
 * class ListNode(_x: Int = 0, _next: ListNode = null) {
 *   var next: ListNode = _next
 *   var x: Int = _x
 * }
 */
object Solution {
    def sortList(head: ListNode): ListNode = {
        if (head == null || head.next == null) {
            return head
        }
        val (first, second) = splitList(head)
        mergeLists(sortList(first), sortList(second))
    }

    def splitList(head: ListNode): (ListNode, ListNode) = {
        var slow = head
        var fast = head
        var pre = slow
        while (fast != null && fast.next != null) {
            pre = slow
            slow = slow.next
            fast = fast.next.next
        }
        pre.next = null
        (head, slow)
    }

    private def mergeLists(first: ListNode, second: ListNode): ListNode = {
        val res = new ListNode(0)
        var cur = res
        var (firstPtr, secondPtr) = (first, second)

        while (firstPtr != null || secondPtr != null) {
            if (firstPtr != null && (secondPtr == null || firstPtr.x <= secondPtr.x)) {
                cur.next = firstPtr
                firstPtr = firstPtr.next
            } else {
                cur.next = secondPtr
                secondPtr = secondPtr.next
            }
            cur = cur.next
        }

        res.next
    }
}