leetcode148:排序链表

package com.mxnet;

public class Solution148 {

    public static void main(String[] args) {

    }

    /**
     * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
     * @param head
     * @return
     * 思路：
     * 1. 使用归并排序的思路，即依次二分链表再合并
     * 2. 递归的将链表二分，递归结束的条件为子链表只剩下一个元素或者子链表为空
     * 3. 对于而二分的子链表，使用链表的从小到达排序算法将其合并
     * 4. 最后则得到完整升序的链表
     */
    public ListNode sortList(ListNode head) {
        return sortList(head,null);
    }

    /**
     * 递归将一条链表进行排序
     * @param head
     * @param tail
     * @return
     */
    public ListNode sortList(ListNode head, ListNode tail) {
        //递归结束条件：链表中没有元素或者只有一个元素
        if (head == null){
            return head;
        }
        if (head.next == tail){
            head.next = null;
            return head;
        }
        //创建快慢指针
        ListNode fast = head;
        ListNode slow = head;
        //快指针移动一次，慢指针移动两次，当快指针到达链表末尾时，慢指针刚好到链表中间
        while (fast != tail){
            fast = fast.next;
            slow = slow.next;
            if (fast != tail){
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        //递归排序并组合
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);
        ListNode merge = merge(list1, list2);
        return merge;
    }

    /**
     * 将两条链表由小到大合并
     * @param head1 链表1
     * @param head2 链表2
     * @return
     * 思路：
     * 1. 创建一条新链表用于保存排好序的链表
     * 2. 循环将两条链表最前边的值进行比较，每次取出最小的挂在到新链表上
     * 3. 若两条链表长度不一致，则在循环结束后将较长链表后半部分挂在新链表后边
     */
    public ListNode merge(ListNode head1, ListNode head2){
        //创建新链表保存排好序的链表
        ListNode dummyHead = new ListNode();
        //创建辅助链表
        ListNode temp = dummyHead;
        ListNode temp1 = head1;
        ListNode temp2 = head2;
        //每次通过节点大小取出一个节点链接到新链表后面
        while (temp1 != null && temp2 != null){
            if (temp1.val <= temp2.val){
                temp.next = temp1;
                temp1 = temp1.next;
            }else if (temp1.val > temp2.val){
                temp.next = temp2;
                temp2 = temp2.next;
            }
            //temp辅助指针后移
            temp = temp.next;
        }
        //当其中一条链表为空，另一条不为空时，将不为空链表连接到后面
        if (temp1 != null){
            temp.next = temp1;
        }else if (temp2 != null){
            temp.next = temp2;
        }
        return dummyHead.next;
    }
}