链表排序--归并排序

￡神魔★判官ぃ 2022-06-07 07:10 155阅读 0赞

要求在空间复杂度为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;
         }