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
import com_github_leetcode.ListNode
/*
* Example:
* var li = ListNode(5)
* var v = li.`val`
* Definition for singly-linked list.
* class ListNode(var `val`: Int) {
* var next: ListNode? = null
* }
*/
@Suppress("NAME_SHADOWING")
class Solution {
fun sortList(head: ListNode?): ListNode? {
if (head == null || head.next == null) {
return head
}
// Step 1: split the list into halves
var prev: ListNode? = null
var slow = head
var fast = head
while (fast != null && fast.next != null) {
prev = slow
fast = fast.next!!.next
slow = slow!!.next
}
prev!!.next = null
// step 2: sort each half
val l1 = sortList(head)
val l2 = sortList(slow)
// step 3: merge the two halves
return merge(l1, l2)
}
private fun merge(l1: ListNode?, l2: ListNode?): ListNode? {
var l1 = l1
var l2 = l2
val result = ListNode(0)
var tmp: ListNode? = result
while (l1 != null && l2 != null) {
if (l1.`val` < l2.`val`) {
tmp!!.next = l1
l1 = l1.next
} else {
tmp!!.next = l2
l2 = l2.next
}
tmp = tmp.next
}
if (l1 != null) {
tmp!!.next = l1
}
if (l2 != null) {
tmp!!.next = l2
}
return result.next
}
}