leetcode148. 排序链表

方法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;}
}