博客

题目

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

示例 ：



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

输出：[1,2,3,4]

提示：

1、链表中节点的数目在范围 [0, 5 * 104] 内；

2、-105 <= Node.val <= 105。

注意点

1、归并排序其实就是使用分治（将问题分(divide)成一些小的问题然后递归求解）的思想来实现排序的，其主要的操作就是将两个已经有序的序列进行合并成一个有序的链表；

2、使用分治思想，所以需要寻找中间节点，链表寻找中间节点一般使用快慢指针的方式进行求解；

3、主要步骤如下：

• 判断链表是否为空，如果为空，则直接返回null；（该题中的链表为左闭右开，即包括head，不包括tail）
• 判断链表是否只有一个节点，如果只有一个节点，返回当前节点，并分割；（保证以head为头节点的链表一定是有序的）
• 如果链表的节点树大于1（无序），则从中间将链表分割为两个链表；
• 对左右两个链表分别进行排序；（此题递归使用归并排序，其实也可以使用其他排序方式）
• 合并这两个有序的两边，并返回结果。
  
  

实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }

	// 归并排序（head：表示链表第一个节点，tail：表示尾节点（不是最后一个节点，链表包括head，不包括tail））
    public ListNode sortList(ListNode head, ListNode tail) {
    	// 链表为空，直接返回null
        if (head == null) {
            return head;
        }

		// 链表只有一个节点，直接返回该节点（一个节点一定有序）
        if (head.next == tail) {
        	// 将有序链表的分隔开（保证以head为头节点的链表一定是有序的）
            head.next = null;
            return head;
        }

		// 慢指针（一次走一步）
        ListNode slow = head;
        // 块指针（一次走两步）
        ListNode fast = head;
        // 寻找中间节点（快慢指针获取中间节点）
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            // 快指针走第二步时也必须判断是否到达最后一个节点（避免越界或空指针）
            if (fast != tail) {
                fast = fast.next;
            }
        }

		// 获取中间节点（将链表分成两部分）
        ListNode mid = slow;
        // 对左边链表进行归并排序
        ListNode sortList1 = sortList(head, mid);
        // 对右边链表进行归并排序
        ListNode sortList2 = sortList(mid, tail);
        // 合并两个有序链表
        ListNode sorted = merge(sortList1, sortList2);

		// 返回结果
        return sorted;
    }

	// 合并两个有序链表
    public ListNode merge(ListNode sortList1, ListNode sortList2) {
    	// 创建新链表（保存合并后的有序链表）
        ListNode dummy = new ListNode(-1);
        // p指针（指向新链表的当前节点）
        ListNode p = dummy;
        // p1指针（指向第一个有序链表的当前节点）
        ListNode p1 = sortList1;
        // p2指针（指向第二个有序链表的当前节点）
        ListNode p2 = sortList2;
        // 合并等长部分的链表
        while (p1 != null && p2 != null) {
            if (p1.val <= p2.val) {
                p.next = p1;
                p = p.next;
                p1 = p1.next;
            } else {
                p.next = p2;
                p = p.next;
                p2 = p2.next;
            }
        }

		// 合并剩余部分
        if (p1 != null) {
            p.next = p1;
        }
        if (p2 != null) {
            p.next = p2;
        }

        return dummy.next;
    }
}