时间复杂度为: nlog(n)
归并排序的时间复杂度是 nlog(n)
解题思路:
1.找到链表的中间节点
2.注意:要保证从head
到mid
之后,就不能继续排序
所以要将mid
.next
备份为midNext
,并将mid
.next
置为null
3.归并排序链表
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * * @param head ListNode类 * @return ListNode类 */ public ListNode sortList (ListNode head){ // write code here if(head == null || head.next == null){ return head; } ListNode mid = getMidNode(head); // 下面的环节重要 ListNode midNext = mid.next; mid.next = null; // 上面的环节重要 ListNode leftPart = sortList(head); ListNode rightPart = sortList(midNext); ListNode dummy = new ListNode(-1); ListNode cur = dummy; while(leftPart != null && rightPart != null){ if(leftPart.val <= rightPart.val){ cur.next = new ListNode(leftPart.val); leftPart = leftPart.next; }else{ cur.next = new ListNode(rightPart.val); rightPart = rightPart.next; } cur = cur.next; } while(leftPart != null){ cur.next = new ListNode(leftPart.val); cur = cur.next; leftPart = leftPart.next; } while(rightPart != null){ cur.next = new ListNode(rightPart.val); cur = cur.next; rightPart = rightPart.next; } return dummy.next; } public ListNode getMidNode(ListNode head){ if(head == null || head.next == null) return head; ListNode slow = head; ListNode fast = head; while(fast.next != null && fast.next.next != null){ slow = slow.next; fast = fast.next.next; } return slow; } }