[数据结构与算法]【LeetCode148】排序链表

对一个链表排序，归并思路

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
        }
        return sortList(head, tail);
    }

    // 归并排序
    public ListNode sortList(ListNode head, ListNode tail) {
        if (head == tail) {
            return head;
        }
        ListNode mid = findMid(head, tail);
        ListNode head1 = head;//获取两个链表头尾指针
        ListNode head2 = mid.next;
        ListNode tail1 = mid;
        ListNode tail2 = tail;
        tail1.next = null;//注意断开两个链表的联系
        tail2.next = null;
        ListNode node1 = sortList(head1, tail1);
        ListNode node2 = sortList(head2, tail2);
        ListNode mergedList = merge(node1, node2);
        return mergedList;
    }

    // 寻找中间节点
    public ListNode findMid(ListNode head, ListNode tail) {
        ListNode fast = head;
        ListNode slow = head;
        if (head.next == tail) {
            return head;
        }
        while (fast != tail) {
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            } else {
                break;
            }
            slow = slow.next;
        }
        return slow;
    }

    // 合并两个链表
    public ListNode merge(ListNode head_1, ListNode head_2) {
        ListNode head = new ListNode();
        ListNode tail = head;
        while (head_1 != null && head_2 != null) {
            if (head_1.val <= head_2.val) {
                tail.next = head_1;
                head_1 = head_1.next;
            } else {
                tail.next = head_2;
                head_2 = head_2.next;
            }
            tail = tail.next;
        }
        while (head_1 != null) {
            tail.next = head_1;
            head_1 = head_1.next;
            tail = tail.next;
        }
        while (head_2 != null) {
            tail.next = head_2;
            head_2 = head_2.next;
            tail = tail.next;
        }
        return head.next;
    }
}