Leetcode:148. 排序链表

#Leetcode: 141.排序链表

题目描述

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

思路

思路1

使用快排实现，值修改

思路2

使用归并排序，实现平均复杂度$O(n)$,因为链表可以直接引用空间，所以可以不用额外的$O(nlogn)$空间，需要注意获取中间节点的快指针位置初始设置

代码

思路1代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        
        quickSort(head, null);
        
        return head;
    }
    
    private void quickSort(ListNode head, ListNode end){
        if (head != end){
            ListNode midNode = getPartition(head, end);
            quickSort(head, midNode);
            quickSort(midNode.next, end);
        }
    }
    
    private ListNode getPartition(ListNode head, ListNode end){
        ListNode getNode = head;
        int getNum = head.val;
        ListNode pre = head.next;
        
        while(pre != null){
            if (pre == end){
                break;
            }
            if (pre.val < getNum){
                getNode = getNode.next;
                int tempNum = pre.val;
                pre.val = getNode.val;
                getNode.val = tempNum;
            }
            pre = pre.next;
        }
        
        int tempNum = getNode.val;
        getNode.val = head.val;
        head.val = tempNum;
        
        return getNode;
    }
}

代码2

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        
        ListNode pre = head.next;
        ListNode middle = head;
        while (pre != null && pre.next != null){
            pre = pre.next.next;
            middle = middle.next;
        }
        
        pre = middle.next;
        middle.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(pre);
        
        ListNode result = new ListNode(0);
        ListNode temp = result;
        while (left != null && right != null){
            if (left.val < right.val){
                temp.next = left;
                left = left.next;
            }else{
                temp.next = right;
                right = right.next;
            }
            temp = temp.next;
        }
        temp.next = right;
        if (left != null){
            temp.next = left;
        }
        
        return result.next;
    }
}

复杂度分析

思路1时间复杂度

最坏$O(n^2)$，平均$O(nlogn)$

思路1空间复杂度

$O(1)$

思路2时间复杂度

$O(nlogn)$

思路2空间复杂度

$O(1)$