题目链接：Insertion Sort List

Sort a linked list using insertion sort.

这道题的要求是对链表进行插入排序。

插入排序，就是和玩扑克差不多，每次拿到一张新牌，会从一侧向另一侧查找，直到找到合适位置，将其插进去，并保证手中的牌仍有续。

  1. 直接插入

而对于链表，采用同样的操作。将链表分为2部分：已排好序的部分和未排序的剩余rem部分。接下来，对每一个剩余节点，都在已排好序的部分中从左往右第查找，直到链表尾或者出现大于rem节点数值的节点停止查找。然后将rem指向的节点插入，并将rem后移一位。

时间复杂度：O(n2)

空间复杂度：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

class Solution
{
public:
    ListNode *insertionSortList(ListNode *head)
    {
        if(head == NULL || head -> next == NULL)
            return head;
        
        // 加头，便于后续操作
        ListNode *h = new ListNode(0);
        h -> next = head;
        
        // 将链表在第一个节点后面切割，从第二个节点开始为剩余部分rem
        ListNode *rem = h -> next -> next;
        h -> next -> next = NULL;
        
        // 执行插入操作，直到剩余部分rem没有节点
        while(rem != NULL)
        {
            // 找到要插入节点的位置
            ListNode *p = h;
            while(p -> next != NULL && p -> next -> val < rem -> val)
                p = p -> next;
            
            // 插入节点
            ListNode *temp = rem -> next;
            rem -> next = p -> next;
            p -> next = rem;
            rem = temp;
        }
        
        return h -> next;
    }
};

  1. 利用Hash

上面链表插入排序的时间复杂度为O(n2)，其中每次找到需要插入的位置时的复杂度为O(n)，因此，可以用hash进行快速找到要插入位置。由于c++中的map是由红黑树实现的，已经按key值进行排序了，因此，就可以用map在O(logn)时间复杂度找到要插入位置。

  • 如果map中没有要插入节点，将其放入map中，然后找到其迭代器it，令it自减（如果it已经指向头节点，那么前一节点就是h了），这样就指向其前一节点了，就可以插入了。
  • 如果map中已存在要插入节点，那么对应的value就是要插入位置的前一节点，然后再重新将该节点放到map中即可。

这样排序还是稳定的。。。

时间复杂度：O(nlogn)

空间复杂度：O(n)

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
45
46
47

class Solution
{
public:
    ListNode *insertionSortList(ListNode *head)
    {
        if(head == NULL || head -> next == NULL)
            return head;
        
        // 加头，便于后续操作
        ListNode *h = new ListNode(0);
        h -> next = head;
        
        // 将链表在第一个节点后面切割，从第二个节点开始为剩余部分rem
        ListNode *rem = h -> next -> next;
        h -> next -> next = NULL;
        
        map<int, ListNode *> hash;
        hash[h -> next -> val] = h -> next;
        
        // 执行插入操作，直到剩余部分rem没有节点
        while(rem != NULL)
        {
            ListNode *p = NULL;
            // 找到要插入节点的位置p
            auto it = hash.find(rem -> val);
            if(it == hash.end())
            {
                hash[rem -> val] = rem;
                it = hash.find(rem -> val);
                p = it == hash.begin() ? h : (-- it) -> second;
            }
            else
            {
                p = it -> second;
                hash[rem -> val] = rem;
            }
            
            // 插入节点
            ListNode *temp = rem -> next;
            rem -> next = p -> next;
            p -> next = rem;
            rem = temp;
        }
        
        return h -> next;
    }
};