GuilinDev

Lc0147

05 August 2008

* 147 - Insertion Sort List

原题概述

Sort a linked list using insertion sort.


A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list.
With each iteration one element (red) is removed from the input data and inserted in-place into the sorted list

Algorithm of Insertion Sort:

  1. Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
  2. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.
  3. It repeats until no input elements remain.

Example 1:

1
2

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

1
2

Input: -1->5->3->4->0
Output: -1->0->3->4->5

题意和分析

首先，For God’s sake, don’t try sorting a linked list during the interview.所以我们这道题练习链表的基本操作。

要求对链表实现插入排序，这是一种O(n^2)复杂度的算法，就是每次循环找到一个元素在当前排好的结果中相对应的位置，然后插进去，经过n次迭代之后就得到排好序的结果了。了解了思路之后就是链表的基本操作了，搜索并进行相应的插入。时间复杂度是排序算法的O(n^2)，空间复杂度是O(1)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(-1);
        
        // insert 每次寻找需要插入的位置
        insert.next = head;
                
        ListNode prev = head; // 已排序部分的最右边节点
        ListNode curr = head.next; // 未排序部分的最左边节点
        
        while (curr != null) {
            ListNode insert = dummy;
            while (curr.val > insert.next.val && insert != prev) {
                insert = insert.next;
            }
            
            if (insert == prev) { // 当前节点的位置是当前有序部分的最右边
                curr = curr.next;
                prev = prev.next;
            } else { // 插入到有序数组的左边或中间
                prev.next = prev.next.next;
                ListNode temp = insert.next;
                insert.next = curr;
                curr.next = temp;
                
                curr = prev.next;
            }
        }
        return dummy.next;
    }
}
This site is open source. Improve this page.