LeetCode百题【排序链表】

题目描述

给你链表的头结点 head ，请将其按升序排列并返回 排序后的链表 。

示例 1：

1 2	`输入：head = [4,2,1,3] 输出：[1,2,3,4]`

示例 2：

1 2	`输入：head = [-1,5,3,4,0] 输出：[-1,0,3,4,5]`

示例 3：

1 2	`输入：head = [] 输出：[]`

提示：

链表中节点的数目在范围 [0, 5 * 10^4] 内
-10^5 <= Node.val <= 10^5

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

解法

归并排序
- 找到链表的中点，以中点为分界，将链表拆分成两个子链表。
  - 寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 11步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
- 对两个子链表分别排序。
- 将两个排序后的子链表合并，得到完整的排序后的链表。可以使用「合并两个有序链表」的做法，将两个有序的子链表进行合并。

class Solution {

    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }

    /**
     * 找到中间数分解为两个有序链表后合并
     * @param head 头结点
     * @param tail 尾结点
     * @return
     */
    public ListNode sortList(ListNode head,ListNode tail){
        //1.定义递归出口
        if (head==null){
            return head;
        }
        if (head.next==tail){
            head.next=null;
            return head;
        }
        //2.寻找中点，快慢指针
        //快的速度为2，慢的速度为1，快的走完后，慢的指向中点
        ListNode slow=head;
        ListNode fast=head;
        while (fast!=tail){
            slow=slow.next;
            fast=fast.next;
            if (fast!=tail){
                fast=fast.next;
            }
        }
        ListNode mid=slow;
        //3.一分为二，进行递归
        ListNode list1=sortList(head, mid);
        ListNode list2=sortList(mid, tail);
        //4.进行两条有序链表合并
        ListNode sorted = merge(list1, list2);
        return sorted;
    }

    /**
     * 合并两条有序的链表，简单迭代
     * @param list1
     * @param list2
     * @return 合并后有序的链表
     */
    public ListNode merge(ListNode list1,ListNode list2){
        ListNode pre=new ListNode(-1);//存放先前的值
        ListNode head=pre;//头指针，用于返回
        while(list1!=null&&list2!=null){
            //都没有遍历完
            if (list1.val<list2.val){
                pre.next=list1;
                list1=list1.next;
            }else {
                pre.next=list2;
                list2=list2.next;
            }
            pre=pre.next;
        }
        //任意一条遍历完后，剩下的直接接上
        if (list1==null){
            pre.next=list2;
        }else {
            pre.next=list1;
        }
        return head.next;
    }
}