Insertion Sort List

描述

Sort a linked list using insertion sort.

分析

无

代码

  1. // Insertion Sort List
  2. // 时间复杂度O(n^2)，空间复杂度O(1)
  3. public class Solution {
  4.     public ListNode insertionSortList(ListNode head) {
  5.         ListNode dummy = new ListNode(Integer.MIN_VALUE);
  6.         //dummy.next = head;
  8.         for (ListNode cur = head; cur != null;) {
  9.             ListNode pos = findInsertPos(dummy, cur.val);
  10.             ListNode tmp = cur.next;
  11.             cur.next = pos.next;
  12.             pos.next = cur;
  13.             cur = tmp;
  14.         }
  15.         return dummy.next;
  16.     }
  18.     ListNode findInsertPos(ListNode head, int x) {
  19.         ListNode pre = null;
  20.         for (ListNode cur = head; cur != null && cur.val <= x;
  21.              pre = cur, cur = cur.next)
  22.             ;
  23.         return pre;
  24.     }
  25. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/sorting/insertion-sort/insertion-sort-list.html