题解 | #单链表的排序#
单链表的排序
https://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08
public class Solution {
/**
*
* @param head ListNode类 the head node
* @return ListNode类
*/
public ListNode sortInList (ListNode head) {
// write code here
List<ListNode> lists = new ArrayList<>();
while (head != null) {
ListNode next = head.next;
head.next = null;
lists.add(head);
head = next;
}
while (lists.size() > 1) {
if (lists.size() % 2 == 0) {
List<ListNode> cur = new ArrayList<>();
for (int i = 1 ; i < lists.size() ; i += 2) {
cur.add(mergeSort(lists.get(i-1),lists.get(i)));
}
lists = cur;
} else {
List<ListNode> cur = new ArrayList<>();
for (int i = 1 ; i < lists.size() - 1; i += 2) {
cur.add(mergeSort(lists.get(i-1),lists.get(i)));
}
cur.add(lists.get(lists.size() - 1));
lists = cur;
}
}
return lists.get(0);
}
public ListNode mergeSort(ListNode root1,ListNode root2) {
ListNode vHead = new ListNode(-100);
ListNode work = vHead;
work.next = null;
while (root1 != null && root2 != null) {
if (root1.val < root2.val) {
work.next = root1;
work = work.next;
root1 = root1.next;
} else {
work.next = root2;
work = work.next;
root2 = root2.next;
}
}
while (root1 != null) {
work.next = root1;
work = work.next;
root1 = root1.next;
}
while (root2 != null) {
work.next = root2;
work = work.next;
root2 = root2.next;
}
return vHead.next;
}
}
// 归并排序的想法
