山之高 月出小
月之小 何皎皎
我有所思在远道 一日不见兮
我心悄悄
C++，链表题，在链表上实现插入排序。
仔细一想就发现了在单链表上排序的难处，因为单链表只能往后遍历，而不能往前，因为只有next指针。
所以就想到了用map去记录每个结点的前一个结点，需要注意的是排序的时候要如果改变了next的指向，那必然也要对应修改map。
于是就按数组的类似操作去操作链表来实现插入排序。
/**
* 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) return nullptr;
unordered_map<ListNode *, ListNode *> pre;
ListNode *dummy = new ListNode(0);
dummy->next = head;
ListNode *p = dummy, *q = head;
while (q) {
pre[q] = p;
q = q->next;
p = p->next;
}
p = head;
q = head->next;
while (q) {
if (p->val > q->val) {
ListNode *left = p;
while (left != dummy && left->val > q->val)
left = pre[left];
p->next = q->next;
q->next = left->next;
left->next = q;
pre[q] = left;
pre[q->next] = q;
pre[p->next] = p;
} else p = p->next;
q = p->next;
}
return dummy->next;
}
};
当然这种做法不太好，借助了额外空间。
所有还有一种，但我感觉和题目中说到的插入排序不太一样。
思路就是在原链表的基础上，生成一个新的排序链表。
/**
* 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) {
ListNode *dummy = new ListNode(-1);
while (head) {
ListNode *curr = dummy, *p = nullptr;
while (curr->next && curr->next->val <= head->val) curr = curr->next;
p = head->next;
head->next = curr->next;
curr->next = head;
head = p;
}
return dummy->next;
}
};
