题解 | 单链表的排序

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    
    // public ListNode[] segList(ListNode head) {
    //     if (head == null || head.next == null) {
    //         return new ListNode[] {head, null};
    //     }
    //     // 两个节点的没有处理好
    //     ListNode fast = head;
    //     ListNode slow = head;
    //     if (head.next.next == null) {
    //         fast = head.next;
    //         slow.next = null;
    //         return new ListNode[] {slow, fast};
    //     }
    //     while (fast != null && fast.next != null) {
    //         slow = slow.next;
    //         fast = fast.next.next;
    //     }
    //     ListNode nextNode = slow.next;
    //     slow.next = null;
    //     ListNode slow_list = head;
    //     ListNode fast_list = nextNode;
    //     System.out.println("slow_list");
    //     System.out.println("fast_list\n");
    //     return new ListNode[] {slow_list, fast_list};
    // }

    public ListNode[] segList(ListNode head) {
        ListNode fast = head;
        ListNode slow = head; //4,5
        if (head == null || head.next == null) {
            return new ListNode[] {head, null};
        }
        //fast有next的前提是next存在
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //找到slow的前一个节点
        ListNode newHead = head;
        while (newHead.next != slow && newHead.next != null) {
            newHead = newHead.next;
        }
        newHead.next = null;
        System.out.println("slow_list");
        System.out.println("fast_list\n");
        return new ListNode[] {head, slow};
    }
    public ListNode merge(ListNode slow, ListNode fast) {
        ListNode dummy = new ListNode(0);
        ListNode m = dummy;
        ListNode p = slow;
        ListNode q = fast;
        //  9410 765  014 5679  79
        while (p != null && q != null) {
            if (p.val <= q.val) {
                m.next = p;
                m = p;
                p = p.next;

            } else {
                m.next = q;
                m = q;
                q = q.next;
            }
        }
        if (p != null) {
            m.next = p;
        }
        if (q != null) {
            m.next = q;
        }


        return dummy.next;
    }

    public ListNode sortInList(ListNode head) {
        //忘记设置递归终止条件
        if (head == null || head.next == null) {
            return head;
        }
        ListNode[] list_set = segList(head);
        ListNode slow_list = list_set[0];
        ListNode fast_list = list_set[1];
        ListNode new_slow_list = sortInList(slow_list);
        System.out.println("new_slow_list\n\n");
        ListNode new_fast_list = sortInList(fast_list);
        System.out.println("new_fast_list\n\n");
        return  merge(new_slow_list, new_fast_list);

    }
}

单链表排序 ，要求时间复杂度为nlogn，选择了归并排序。归并排序的核心是不断将两个有序列表合并。在链表中要实现一个分割链表的函数来辅助归并排序的实现。可行的方法是采用快慢指针。如果链表结点是奇数 比如 1 2 3 最终slow指向中间节点，如果是偶数，则将链表均分为两个子链表，slow指向第二个链表的第一个节点。分割的时候踩了一个坑，为了减少一次遍历（去找到slow的前一个节点，然后断开连接），我采用了直接将slow.next 作为第二个链表的开始，具体写法是 下面，但是导致了对于两个节点的子链表 无法分割 从而导致报错。 后面换成将slow的前一个节点和slow断开 ，成为两个链表，则没有这个问题 。但是写法还是不够简练，其实在移动slow和fast的过程就可以定位slow的前一个节点。

同时方法用到了 递归，一定要考虑递归的终止条件

此外，如果需要用到尾插法，可以设置一个虚拟节点dummy 到时候直接返回dummy.next.

头插法好像只有在翻转链表的时候更方便一点^_^hhhhh ，明天再写一遍 使用迭代！！！！

// public ListNode[] segList(ListNode head) {
//     if (head == null || head.next == null) {
//         return new ListNode[] {head, null};
//     }
//     // 两个节点的没有处理好
//     ListNode fast = head;
//     ListNode slow = head;
//     if (head.next.next == null) {
//         fast = head.next;
//         slow.next = null;
//         return new ListNode[] {slow, fast};
//     }
//     while (fast != null && fast.next != null) {
//         slow = slow.next;
//         fast = fast.next.next;
//     }
//     ListNode nextNode = slow.next;
//     slow.next = null;
//     ListNode slow_list = head;
//     ListNode fast_list = nextNode;
//     System.out.println("slow_list");
//     System.out.println("fast_list\n");
//     return new ListNode[] {slow_list, fast_list};
// }