1.代码
public class Solution {
public ListNode sortList(ListNode head) {
// 链表结束的条件
if(head == null || head.next == null){
return head;
}
// 使用归并排序(从底部开始排序,左右两部分,进行链表合并)
ListNode mid = middleNode(head);
ListNode rightNode = mid.next;
mid.next = null;
ListNode left = sortList(head);
ListNode right = sortList(rightNode);
return merge(left, right);
}
//找到链表中间节点
public ListNode middleNode(ListNode head){
ListNode slow = head;
ListNode fast = head;
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
//合并两个有序链表
public ListNode merge(ListNode head1, ListNode head2) {
ListNode p1 = head1;
ListNode p2 = head2;
ListNode dummyNode = new ListNode(-1);
ListNode cur = dummyNode;
while (p1 != null && p2 != null) {
if (p1.val <= p2.val) {
cur.next = p1;
p1 = p1.next;
} else {
cur.next = p2;
p2 = p2.next;
}
cur = cur.next;
}
if (p1 != null) {
cur.next = p1;
} else if (p2 != null) {
cur.next = p2;
}
return dummyNode.next;
}
}