leetcode解题: Insertion Sort List (147)

发表于 | 分类于

Sort a linked list using insertion sort.

解法1：Dummy Node, Insertion Sort O(N^2)

这题一开始想不太清楚，但知道应该用dummy node。实际上，dummy node可以作为一个空的list，用一个指针（head）来记录当前想要插入的node，每一个node在dummy指向的list中找到位置后插入。
这样想就比较清晰了。用到的指针有

  1. cur 记录当前插入的node的指针
  2. p 用来遍历已经排序好的dummy指向的那个list
  3. head 用来遍历原list直到end

C++

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        ListNode* dummy = new ListNode(0);
        // For each node, attach to dummy linked list
        while (head != NULL) {
            ListNode* cur = head;
            head = head->next;
            ListNode* p = dummy;
            while (p->next && p->next->val <= cur->val) {
                p = p->next;
            }
            cur->next = p->next;
            p->next = cur;
        }
        head = dummy->next;
        delete dummy;
        return head;
    }
};

Java

1