题目描述

给定一个链表，请用归并排序的方法，对链表完成排序。

之前一道题中：，我们完成了通过插入排序的方式对链表进行了排序，我们知道插入排序的时间复杂度是O(n^2)，那么我们当然可以想到使用更快速的排序方式，所以本题尝试使用归并排序的方式来实现。

归并排序分析

归并的核心思想就是把一个大集合拆分为两个小集合，再分别对两个小集合进行拆分，直到不能拆分为止，然后对拆分后的小集合进行排序，排序完成后再向上合并，最终合并为一个有序的集合。

那么在之前的基础题中，我们也遇到过如何对两个有序链表进行合并：，所以最终归并的方式只需要对链表进行拆分即可，那么又可以通过快慢指针的方式找到中间节点进行拆分：，所以实际上只要有了前面练习的基础，那么实现归并排序并不困难。

代码实现

public class MergeSortList {
       public static void main(String[] args) {
           ListNode n = new ListNode(1);        ListNode head = n;        for (int i = 2; i < 6; i++) {
               n.next = new ListNode(i);            n = n.next;        }        for (int i = 6; i > 0; i--) {
               n.next = new ListNode(i);            n = n.next;        }        System.out.println(new MergeSortList().sortList(head));    }    public ListNode sortList(ListNode head) {
           //类似数组归并一样，从头尾开始        return sortList(head, null);    }    private ListNode sortList(ListNode head, ListNode tail) {
           //无法继续拆分的情况        if (head == null) {
               return null;        }        //无法继续拆分的情况        if (head.next == tail) {
               head.next = null;            return head;        }        //快慢指针找到中间节点        ListNode slow = head, fast = head;        while (fast != tail && fast.next != tail) {
               slow = slow.next;            fast = fast.next.next;        }        ListNode mid = slow;        //左边继续拆分        ListNode left = sortList(head, mid);        //右边继续拆分        ListNode right = sortList(mid, tail);        //有序链表合并        return merge(left, right);    }    private ListNode merge(ListNode left, ListNode right) {
           ListNode mergeNode = new ListNode();        ListNode help = mergeNode;        //比较两个链表当前的值，值小的链表就把引用赋给mergeNode，并向后移动一位重新赋值给自己，同时help指向值小的那个节点        while (left != null && right != null) {
               if (left.val < right.val) {
                   help.next = left;                left = left.next;            } else {
                   help.next = right;                right = right.next;            }            help = help.next;        }        //最后如果有剩余的节点，就一次性链上去        help.next = left == null ? right : left;        return mergeNode.next;    }}

转载地址：http://thlrb.baihongyu.com/

你可能感兴趣的文章