目录
- 1.题目
- 2.思路
- 3.代码实现（Java）
1.题目
给你链表的头结点 head，请将其按升序排列并返回排序后的链表。
进阶：你可以在 O(nlogn) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-list
2.思路
（1）采用LeetCode147.对链表进行插入排序的中时间复杂度为O(n2)的插入排序算法，具体步骤可以查看该文章，此处不再赘述，但是该算法在LeetCode上运行时会显示超出时间限制的提示！
3.代码实现（Java）
//（1）思路1
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
if(head==null){
return head;
}
//引入preHead:便于在head节点之前插入节点
ListNode preHead=new ListNode(0);
preHead.next=head;
//finalNode:已排序部分的最后一个节点，初始值为head
ListNode finalNode=head;
//当前待排序节点，初始值为head.next
ListNode currNode=head.next;
while(currNode!=null){
if(finalNode.val<=currNode.val){
//已排序部分的最后一个节点值≤当前待排序节点值，finalNode后移一个节点即可
finalNode=finalNode.next;
}else{
//已排序部分的最后一个节点值>当前待排序节点值
//从链表头开始遍历，tmpNode是插入节点currNode位置的前一个节点
ListNode tmpNode=preHead;
while(tmpNode.val<=currNode.val){
tmpNode=tmpNode.next;
}
//将currNode插入到tmpNode之后，具体过程可查看上面的图片
finalNode.next=currNode.next;
currNode.next=tmpNode.next;
tmpNode.next=currNode;
}
//当前待排序节点已完成排序，currNode向后移动一个节点
currNode=finalNode.next;
}
return preHead.next;
}
}