LeetCode : 148. Sort List 排序链表

ゞ浴缸里的玫瑰 2021-06-24 16:11 352阅读 0赞

**试题**  
Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3  
Output: 1->2->3->4  
Example 2:

Input: -1->5->3->4->0  
Output: -1->0->3->4->5

**代码**  
回顾nlog(n)的数组排序算法，一个关键点就是找到中点。在链表中我们需要使用快慢指针来解决。  
归并算法如下：

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode sortList(ListNode head) {
    //         一个节点无需排序
            if(head==null || head.next==null) return head;
            
    //         获取中节点，并将链表拆分成两部分
            ListNode mid = getMid(head);
            
    //         合并两链表
            return mergeLists(sortList(head),sortList(mid));
            
        }
        
        public ListNode getMid(ListNode head){
            ListNode slow = head;
            ListNode fast = head;
            ListNode tail = head;
            while(fast!=null && fast.next!=null){
                tail = slow;
                slow = slow.next;
                fast = fast.next.next;
            }
            tail.next = null;
            return slow;
        }
        
        public ListNode mergeLists(ListNode l1, ListNode l2){
            ListNode dummy = new ListNode(0);
            ListNode cur = dummy;
            while(l1!=null && l2!=null){
                if(l1.val<l2.val){
                    cur.next = l1;
                    l1 = l1.next;
                }else{
                    cur.next = l2;
                    l2 = l2.next;
                }
                cur = cur.next;
            }
            
            if(l1!=null){
                cur.next = l1;
            }
            if(l2!=null){
                cur.next = l2;
            }
            return dummy.next;
        }
    }