插入排序

对链表进行插入排序，是最简单的一种链表排序算法，用于插入排序是迭代的，所以每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。重复直到所有输入数据插入完为止。
插入排序的时间复杂度为O(N^2)，空间复杂度为O（1）

class Solution { 



public ListNode insertionSortList(ListNode head) { 



ListNode move=head;

ListNode emptyHead=new ListNode();

emptyHead.next=head;

while(move!=null&&move.next!=null){ 



if(!reInsert(move,emptyHead)) 

move=move.next;

}

return emptyHead.next;

}

private Boolean reInsert(ListNode node,ListNode emptyHead){ 



ListNode temp=node.next;

node.next=temp.next;

while(emptyHead!= node){ 



if(temp.val<=emptyHead.next.val){ 



temp.next=emptyHead.next;

emptyHead.next=temp;

return true;

}

emptyHead=emptyHead.next;

}

temp.next=node.next;

node.next=temp;

return false;

}

}

归并排序

对于归并排序排序在数组排序中的运用，详细请点击此处。这里主要介绍归并排序在链表排序中的运用。
在使用归并排序算法进行链表排序时，其基本思想是将链表细分成一个个子链表，将子链表进行排序，然后再将相邻的两个有序子链表进行合并，得到更长的有序链表，最后一步步得到整个有序链表，子链表进行合并排序时需要用到合并两个有序链表算法。
归并链表排序的实现方式一共有两种，递归实现和非递归实现，两种实现方式的时间复杂度都是O(nlogn），但是由于递归实现调用函数时需要消耗大量栈空间，所以递归调用的空间复杂度是O（logn）。对于非递归调用，空间复杂度就是O（1）。

递归代码：

class Solution { 



public ListNode sortList(ListNode head) { 



if(head==null)

return head;

return mergeSort(head);

}

public ListNode mergeSort(ListNode head){ 



if(head.next==null)

return head;

ListNode slow=head;

ListNode fast=head;

while(fast!=null&&fast.next!=null){ 



fast=fast.next.next;

if(fast!=null)

slow=slow.next;

}

ListNode tempHead=slow.next;

slow.next=null;

ListNode left=mergeSort(head);

ListNode right=mergeSort(tempHead);

head=mergeList(left,right);

return head;

}

public ListNode mergeList(ListNode head,ListNode tempHead){ 



ListNode emptyHead=new ListNode(0,head);

ListNode move=emptyHead;

while(head!=null&&tempHead!=null){ 



if(head.val<= tempHead.val){ 



move.next=head;

head=head.next;

}else{ 



move.next=tempHead;

tempHead=tempHead.next;

}

move=move.next;

}

move.next=head==null?tempHead:head;

return emptyHead.next;

}

}

非递归代码：

class Solution { 



public ListNode sortList(ListNode head) { 



if(head==null)

return null;

ListNode end=head;

int length=0;

while(end!=null){ 



length++;

end=end.next;

}

ListNode emptyHead = new ListNode(0, head);

for(int i=1;i


ListNode prev = emptyHead;

ListNode cur = emptyHead.next;

while(cur!=null) { 



ListNode start1 =cur;

for (int j = 1; j < i&&cur.next!=null; j++) { 



cur = cur.next;

}

ListNode start2 = cur.next;

cur.next = null;

cur = start2;

for (int j = 1; j < i && cur != null&&cur.next!=null; j++) { 



cur = cur.next;

}

if(cur!=null){ 



ListNode temp=cur;

cur=cur.next;

temp.next=null;

}

prev.next = mergeList(start1, start2);

while(prev.next!=null){ 



prev=prev.next;

}

}

}

return emptyHead.next;

}

public ListNode mergeList(ListNode head,ListNode tempHead){ 



ListNode emptyHead=new ListNode(0,head);

ListNode move=emptyHead;

while(head!=null&&tempHead!=null){ 



if(head.val<= tempHead.val){ 



move.next=head;

head=head.next;

}else{ 



move.next=tempHead;

tempHead=tempHead.next;

}

move=move.next;

}

move.next=head==null?tempHead:head;

return emptyHead.next;

}

}