题目
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
输入： head = [4,2,1,3] 输出： [1,2,3,4]
题解
我们首先在sortList函数中先定义一个虚拟节点dummy，将其next指向头节点head，方便操作链表，在使用getLength函数获取链表长度len，然后使用步长step进行循环排序，每次将链表分成长度为step的两个子链表，然后将这两个子链表合并成一个有序链表，最后将所有的有序子链表合并成一个有序链表，在定义pre和cur两个指针，这两个指针分别指向虚拟节点dummy和头节点head，然后循环链表，将链表分成长度为step的两个子链表，接下来使用split函数将链表分成长度为step的两个子链表h1和h2，在使用split函数将链表再次分成长度为step的两个子链表，cur指针指向第二个子链表的头节点，最后使用merge函数将两个子链表h1和h2合并成一个有序链表，pre.next指向合并后的链表，使用循环将链表排序完成，最后返回虚拟节点dummy的next节点即为排序后的链表，上述的操作时将链表进行递归分成两个子链表，分别对子链表进行排序，然后将两个有序子链表合并成一个有序链表进行返回了出来
var sortList = function (head) { const dummy = new ListNode(-1) const len = getLength(head) dummy.next = head; for (let step = 1; step < len; step = step * 2) { let pre = dummy, cur = dummy.next while (cur) { let h1 = cur let h2 = split(h1, step) cur = split(h2, step) pre.next = merge(h1, h2) while (pre.next) { pre = pre.next } } } return dummy.next function getLength(head) { let i = 0 while (head) { i++ head = head.next } return i } function merge(l1, l2) { let head = new ListNode(-1), pre = head while (l1 && l2) { if (l1.val < l2.val) { pre.next = l1 l1 = l1.next } else { pre.next = l2 l2 = l2.next } pre = pre.next } pre.next = l1 ? l1 : l2 return head.next } function split(head, step) { if (head == null) return null let pre = head, next = null for (let i = 1; i < step && pre.next; i++) { pre = pre.next } next = pre.next pre.next = null return next } };
