链表排序--归并排序-蒲公英云

链表排序--归并排序

要求在空间复杂度为O(1)的情况下对链表进行排序，在不考虑时间复杂度的情况下可以考虑冒泡排序，只对链表中的值进行操作，这样时间复杂度为O（n^2）。用归并排序，时间复杂度为O（nlogn）。以下为归并排序代码实现

public ListNode sortList(ListNode head) {
         if(head == null || head.next == null)
             return head;
         ListNode mid = getMidNode(head);
         ListNode next = mid.next;
         mid.next = null;
         ListNode left = sortList(head);
         ListNode right = sortList(next);
         head = MergeListNode(left, right);
         return head;
     }
     private static ListNode getMidNode(ListNode head){
         if(head == null || head.next == null)
             return null;
         ListNode fast = head.next;
         ListNode slow = head;
         while(fast != null && fast.next!= null){
             slow = slow.next;
             fast = fast.next.next;
         }
         return slow;
     }
     private static ListNode MergeListNode(ListNode left, ListNode right){
         ListNode temp = new ListNode(0);
         ListNode temp_node = temp;
         while(left != null && right != null){
             if(left.val < right.val){
                 temp_node.next = left;
                 left = left.next;
             }else{
                 temp_node.next = right;
                 right = right.next; 
             }
             temp_node = temp_node.next;
         }
         if(left != null)
             temp_node.next = left;
         if(right != null)
             temp_node.next = right;
         return temp.next;
     }