LeetCode_Sorting_148. Sort List 排序連結清單【快速排序試錯，歸并排序】【java】【中等】

目錄

​​一，題目描述​​

​​英文描述​​

​​中文描述​​

​​示例與說明​​

​​二，解題思路​​

​​三，AC代碼​​

​​Java​​

​​四，解題過程​​

​​第一博​​

​​第二搏​​

一，題目描述

英文描述

Given the head of a linked list, return the list after sorting it in ascending order.

中文描述

給你連結清單的頭結點 head ，請将其按 升序 排列并傳回 排序後的連結清單 。

進階：

常數級空間複雜度下，對連結清單進行排序嗎？

示例與說明

來源：力扣（LeetCode）

連結：​​​力扣​​ 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

二，解題思路

官方給出的題解是歸并排序。快速排序很明顯會被針對。。。

歸并排序的話，主要問題就是如何定位中間位置了。

定位

這裡可以采用快慢指針的方法。

初始化在同一位置，快指針一次走兩步，慢指針一次走一步。等快指針走到連結清單末尾，滿指針所指節點的下一個節點就是中間位置。

連結清單合并 

至于連結清單合并，這個比數組形式還要簡單高效，畢竟不需要重開數組。

簡單的方法就是聲明一個空的頭節點和指針p（該指針指向下一個節點要插入的位置），然後不斷的移動左右連結清單的指針即可。

三，AC代碼

Java

class Solution {
    public ListNode merge (ListNode p1, ListNode p2) {
        ListNode head = new ListNode(), p = head;
        while (p1 != null && p2 != null) {
            if (p1.val < p2.val) {
                p.next = p1;
                p1 = p1.next;
            } else {
                p.next = p2;
                p2 = p2.next;
            }
            p.next.next = null;
            p = p.next;
        }
        while (p1 != null) {
            p.next = p1;
            p1 = p1.next;
            p.next.next = null;
            p = p.next;
        }
        while (p2 != null) {
            p.next = p2;
            p2 = p2.next;
            p.next.next = null;
            p = p.next;
        }
        return head.next;
    }
    public ListNode mergeSort(ListNode head) {
        if (head == null || head.next == null) return head;     // !!!注意邊界，容易出現堆棧溢出錯誤
        ListNode fast = head, slow = head;                      // 通過快慢指針定位中間節點
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode p1 = mergeSort(slow.next);
        slow.next = null;                                       // 将連結清單分成兩段
        ListNode p2 = mergeSort(head);
        return merge(p1, p2);
    }
    public ListNode sortList(ListNode head) {
        return mergeSort(head);
    }
}      

四，解題過程

第一博

先嘗試了簡單的快速排序方法（選取head作為pivot）

class Solution {
    public ListNode partation (ListNode head, ListNode left, ListNode right) {
        if (head == null) return null;
        ListNode pivot = head,p = head.next, tem;// 選取頭節點作為pivot
        while (p != null) {
            tem = p;
            p = p.next;
            if (tem.val < pivot.val) {
                tem.next = left.next;
                left.next = tem;
            } else {
                tem.next = right.next;
                right.next = tem;
            }
        }
        return pivot;
    }
    public ListNode quickSort(ListNode head) {
        if (head == null) return null;
        ListNode left = new ListNode(), right = new ListNode();
        ListNode mid = partation(head, left, right);
        ListNode newLeft = quickSort(left.next);// 遞歸處理左半部分
        ListNode newRight =  quickSort(right.next);// 遞歸處理右半部分
        // 将左半部分、pivot、右半部分進行合并
        if (newLeft != null) {
            ListNode tem = newLeft;
            while (tem.next != null) tem = tem.next;
            if (mid != null) {
                tem.next = mid;
                tem = tem.next;
            }
            tem.next = newRight;
        } else if (mid != null) {
            newLeft = mid;
            newLeft.next = newRight;
        } else {
            newLeft = newRight;
        }
        return newLeft;
    }
    public ListNode sortList(ListNode head) {
        return quickSort(head);
    }
}      

第二搏