本文共 4634 字，大约阅读时间需要 15 分钟。

链接：

大意：

对一个链表进行插入排序，要求使用原地算法（即空间复杂度为O(1)）。例子：

思路：

插入排序的链表实现。但是实现的效率并不高，原因可能就是插入排序时间复杂度太大的缘故。

代码：

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {    public ListNode insertionSortList(ListNode head) {        if (head == null || head.next == null)            return head;        ListNode newHead = new ListNode(0);        while (head != null) {            ListNode work = newHead.next, pre = newHead, tmp = head.next;            while (work != null && work.val < head.val) {                pre = work;                work = work.next;            }            if (work == null) {                pre.next = head;                head.next = null;            } else {                ListNode old = pre.next;                pre.next = head;                head.next = old;            }            head = tmp;        }        return newHead.next;    }}

结果：

结论：

如果不规定使用何种方法进行链表排序，则时间效率可以提升。

改进一：（快速排序）

使用基于快排的内置排序算法对链表排序。

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {    public ListNode insertionSortList(ListNode head) {        if (head == null || head.next == null)            return head;        ArrayList
   
     list = new ArrayList<>();        while (head != null) {            list.add(head);            head = head.next;        }        Collections.sort(list, new Comparator
    
     (){            public int compare(ListNode o1, ListNode o2) {                return o1.val - o2.val;            }        });        ListNode newHead = list.get(0), work = newHead;        int i = 1;        while (i < list.size()) {            work.next = list.get(i++);            work = work.next;        }        work.next = null;        return newHead;    }}
    
   

改进二（归并排序）：

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {    public ListNode insertionSortList(ListNode head) {        if (head == null || head.next == null)            return head;        return merge(head);    }    public ListNode merge(ListNode start) {        if (start == null) // 此段链表没有元素            return null;        if (start.next == null) // 此段链表有一个元素            return start;        if (start.next.next == null) { // 此段链表有两个元素             ListNode tmp = start.next;            start.next = null;            return mergeSort(start, tmp);            }        ListNode slow = start, fast = start;        // 使用快慢指针找到链表中点        while (fast.next != null && fast.next.next != null) {            slow = slow.next;            fast = fast.next.next;        }        // 断链法        ListNode tmp = slow.next;        slow.next = null;        ListNode l1 = merge(start);        ListNode l2 = merge(tmp);        return mergeSort(l1, l2);    }    public ListNode mergeSort(ListNode l1, ListNode l2) {        ListNode newHead = new ListNode(0), work = newHead;        while (l1 != null && l2 != null) {            if (l1.val < l2.val) {                work.next = l1;                l1 = l1.next;            } else {                work.next = l2;                l2 = l2.next;            }            work = work.next;            work.next = null;        }        while (l1 != null) {            work.next = l1;            l1 = l1.next;            work = work.next;        }        while (l2 != null) {            work.next = l2;            l2 = l2.next;            work = work.next;        }        work.next = null;        return newHead.next;    }}

最佳：（精简版归并排序）

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {    public ListNode insertionSortList(ListNode head) {        if(head == null || head.next == null) return head;        ListNode fast = head, slow = head, prev = null;        while(fast != null && fast.next != null){            prev = slow;            slow = slow.next;            fast = fast.next.next;        }        prev.next = null;                ListNode l1 = insertionSortList(head);        ListNode l2 = insertionSortList(slow);                return merge(l1, l2);    }    public ListNode merge(ListNode l1, ListNode l2){        if(l1 == null){            return l2;        }        if(l2 == null){            return l1;        }        if(l1.val < l2.val){            l1.next = merge(l1.next, l2);            return l1;        }else{            l2.next = merge(l1, l2.next);            return l2;        }    }}

转载地址：http://axesi.baihongyu.com/