链表|148. 排序链表

148. 排序链表

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

题目链接： 148. 排序链表
时间复杂度：快排 O(n^2) 超出时间限制

class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null){
            return head;
        }
        ListNode dummy=new ListNode(Integer.MIN_VALUE,null);
        ListNode pointnew=dummy;
        ListNode pointold=head;
        while(pointold!=null){
            while(pointnew!=null&&pointnew.next!=null){
                if(pointold.val<=pointnew.next.val){
                    ListNode next=pointnew.next;
                    ListNode node=new ListNode(pointold.val);
                    pointnew.next=node;
                    node.next=next;
                    pointnew=dummy;
                    break;
                }else{
                    pointnew=pointnew.next;
                }
            }
            if(pointnew.next==null){
                ListNode next=pointnew.next;
                    ListNode node=new ListNode(pointold.val);
                    pointnew.next=node;
                    node.next=next;
                    pointnew=dummy;
            }
            pointold=pointold.next;
        }
        return dummy.next;
    }
}

归并排序O(logn)：

class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        //找中点截断链表
         ListNode fast = head;
         ListNode slow = head;
         ListNode pre=null;
         while(fast!=null&&fast.next!=null){
             pre=slow;
             slow=slow.next;
             fast=fast.next.next;
         }
         //递归截断链表
        pre.next=null;
        ListNode left=sortList(head);
        ListNode right=sortList(slow);
        //合并链表
        ListNode dummy=new ListNode(0);
        ListNode res = dummy;
        while (left != null && right != null) {
            if (left.val < right.val) {
                res.next = left;
                left = left.next;
            } else {
                res.next = right;
                right = right.next;
            }
            res=res.next;
        }
        res.next=left!=null?left:right;
        return dummy.next;
    }
}

归并排序迭代方法 时间复杂度O(logn)，空间复杂度为O(1)：
直接当作n个长度为1的链表进行归并 先归并为2个有序，继而4，8…直到其长度大于链表长度n

public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 获取链表长度
        int length = 0;
        ListNode current = head;
        while (current != null) {
            length++;
            current = current.next;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode left, right, tail;

        // 每次翻倍增加子链表的长度
        for (int step = 1; step < length; step *= 2) {
            current = dummy.next;
            tail = dummy;

            while (current != null) {
                left = current;
                right = split(left, step); // 分割出两个子链表
                current = split(right, step); //划分下一个left
                tail = merge(left, right, tail); // 合并两个子链表
            }
        }

        return dummy.next;
    }

    // 分割链表
    private ListNode split(ListNode head, int step) {
        if (head == null) return null;
        
        for (int i = 1; head.next != null && i < step; i++) {
            head = head.next;
        }
        
        ListNode right = head.next;
        head.next = null;
        return right;
    }

    // 合并两个链表
    private ListNode merge(ListNode l1, ListNode l2, ListNode tail) {
        ListNode current = tail;
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }
        current.next = (l1 != null) ? l1 : l2;
        while (current.next != null) {
            current = current.next;
        }
        return current;
    }