方法1:插入方法进行改进
class Solution {
public ListNode sortList(ListNode head) {
/*
想法:设置两个指针first,last分别指向当前有序子链表的头和尾节点;
并遍历链表,当遍历到的节点值大于last的值时,就将该节点插入到有序子链表表尾
值小于first时,插入到子链表表头,处于二者中间时,就遍历进行插入
*/
if(head == null)
return null;
ListNode first = head,last = head;
ListNode p = head.next;
head.next = null;
while(p != null){
ListNode temp = p.next;
if(p.val >= last.val){
//插入表尾
last.next = p;
p.next = null;
last = p;
}else if(p.val <= first.val){
//插入表头
p.next = first;
first = p;
}else{
// 遍历进行插入
for(ListNode q = first;q != last ;q = q.next){
if(q.next.val > p.val){
p.next = q.next;
q.next = p;
break;
}
}
}
p = temp;
}
return first;
}
}
方法2:自顶向下的归并排序
归并排序的时间复杂度问题:在每一层中进行寻找中间节点+有序链表进行两两合并都需要2n,而归并排序总共会进行logn层处理,因此最终的时间复杂度就是O(nlogn)。
class Solution {
public ListNode sortList(ListNode head) {
/*
自顶向下的归并排序:首先寻找中间节点,在利用归并排序将当前需要排序的链表进行两两分别排序,
最后在通过合并两个有序链表的方式以及递归的方式进行排序。
*/
if(head == null)
return null;
return sortSubList(head,null);
}
//将链表进行排序(tail指向)
public ListNode sortSubList(ListNode head,ListNode tail){
if(head.next == null)
return head;
if(head.next == tail){
head.next = null;
return merge(head,tail);
}
//先找到链表的中间节点
ListNode slow = head,fast = head.next.next;
while(fast != tail){
slow = slow.next;
fast = fast.next;
if(fast != tail)
fast = fast.next;
}
//将左边的子链表表尾指向空指针,右边子链表表尾本就是空指针
ListNode subHead2 = slow.next;
slow.next = null;
ListNode head1 = sortSubList(head,slow);
ListNode head2 = sortSubList(subHead2,tail);
return merge(head1,head2);
}
//将两个子链表进行排序并合并返回合并后的链表头节点
//判断是否到了尾,即是否到了空节点即可
public ListNode merge(ListNode head1,ListNode head2){
ListNode head = new ListNode(-1,null);
ListNode temp = head,temp1 = head1,temp2 = head2;
while(temp1 != null && temp2 != null){
if(temp1.val < temp2.val){
temp.next = temp1;
temp1 = temp1.next;
}else{
temp.next = temp2;
temp2 = temp2.next;
}
temp = temp.next;
}
while(temp1 != null){
temp.next = temp1;
temp1 = temp1.next;
temp = temp.next;
}
while(temp2 != null){
temp.next = temp2;
temp2 = temp2.next;
temp = temp.next;
}
return head.next;
}
}
方法3:自底向上的归并排序
class Solution {
public ListNode sortList(ListNode head) {
/*
自顶向下的归并排序:首先寻找中间节点,在利用归并排序将当前需要排序的链表进行两两分别排序,
最后在通过合并两个有序链表的方式以及递归的方式进行排序。
*/
if(head == null)
return null;
//遍历链表获取链表长度
int length = 0;
ListNode p = head;
while(p != null){
length++;
p = p.next;
}
ListNode hair = new ListNode(-1,head);
for(int subLength = 1;subLength < length;subLength *= 2){
//开始遍历链表,获取子链表,并两两合并
ListNode pre = hair, cur = hair.next;
while(cur != null){
//获取一个的子链表
ListNode head1 = cur;
for(int i = 1;i < subLength && cur.next !=null;i++){
cur = cur.next;
}
ListNode head2 = cur.next;
cur.next = null;
cur = head2;
//再获取一个子链表
for(int i = 1;i < subLength && cur!=null;i++){
cur = cur.next;
}
if(cur != null){
ListNode temp = cur.next;
cur.next = null;
cur = temp;
}
ListNode mergeResult = merge(head1,head2);
//pre指针指向当前两个子链表的前面的一个节点
pre.next = mergeResult;
while(pre.next != null)
pre = pre.next;
}
}
return hair.next;
}
//将两个子链表进行排序并合并返回合并后的链表头节点
//判断是否到了尾,即是否到了空节点即可
public ListNode merge(ListNode head1,ListNode head2){
ListNode head = new ListNode(-1,null);
ListNode temp = head,temp1 = head1,temp2 = head2;
while(temp1 != null && temp2 != null){
if(temp1.val < temp2.val){
temp.next = temp1;
temp1 = temp1.next;
}else{
temp.next = temp2;
temp2 = temp2.next;
}
temp = temp.next;
}
while(temp1 != null){
temp.next = temp1;
temp1 = temp1.next;
temp = temp.next;
}
while(temp2 != null){
temp.next = temp2;
temp2 = temp2.next;
temp = temp.next;
}
return head.next;
}
}