题解 | #单链表的排序#
单链表的排序
https://pre.nowcoder.com/practice/f23604257af94d939848729b1a5cda08
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类 the head node
* @return ListNode类
*/
public ListNode sortInList (ListNode head) {
// 寻找最小的元素，并利用头插法插入到节点
ListNode dummy = new ListNode(Integer.MAX_VALUE);
dummy.next = head;
ListNode sorted = dummy;
while (sorted.next != null) {
ListNode pre = sorted;
ListNode cur = sorted.next;
ListNode pre_min = null;
ListNode min = null;
// 寻找最小的数
while (cur != null) {
if (min == null || cur.val < min.val) {
min = cur;
pre_min = pre;
}
// 继续向后移动指针
cur = cur.next;
pre = pre.next;
}
// 利用头插法插入
pre_min.next = min.next;
min.next = sorted.next;
sorted.next = min;
// 哨兵节点往后移动
sorted = min;
}
return dummy.next;
}
}
