【LeetCode】【算法】148. 排序链表

LeetCode 148. 排序链表

题目

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

思路

思路：归并排序
第一步：切左右，使用快慢指针找到中间节点
第二步：排左右，根据上面找到的中间节点，左右两个链表作为参数递归调用排序方法
第三步：while(leftNode!=null&&rightNode!=null)判断左右链表的结果，进行归并排序
第四步：对于leftNode!=null / rightNode!=null，把不为空的节点接到排好序的链表后面

代码

/**
 * 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) {
        // 归并排序

        // 返回条件
        if (head == null) return head;
        if (head != null && head.next == null) return head;

        // 切左右
        ListNode prevSlowNode = head;
        ListNode slowNode = head;
        ListNode fastNode = head;
        while (fastNode != null && fastNode.next != null) {
            prevSlowNode = slowNode;
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
        }
        prevSlowNode.next = null;

        // 排左右
        ListNode leftNode = sortList(head); // 排左边
        ListNode rightNode = sortList(slowNode); // 排右边

        // 左右归并排序
        ListNode result = new ListNode(); // dummy head
        ListNode cur = result;
        while (leftNode != null && rightNode != null) {
            if (leftNode.val < rightNode.val){
                cur.next = leftNode;
                leftNode = leftNode.next;
            } else {
                cur.next = rightNode;
                rightNode = rightNode.next;
            }
            cur = cur.next;
            cur.next = null;
        }
        if (leftNode != null){
            cur.next = leftNode;
        }
        if (rightNode != null){
            cur.next = rightNode;
        }

        return result.next;
    }
}