使用直接插入排序。值得考虑的是，是否可以使用二分搜索的插入排序？希望有实现了的朋友告诉我。
几道链表类题目做下来，总结出两个技巧：
1.对没有头结点的链表，首先建立伪头结点dummy，这样一来，当算法需要始终维护一个当前指针的父结点指针pre时，就不至于因为在初始时将父结点pre置为NULL而出错。
2.一步两步方法，可以较快的找到链表的近似中间点的指针；如果使用先遍历整个链表确定长度，在遍历半个链表长度找到中间点的方法，时间复杂度为O(1.5N)，而如果同时使用两个指针p1和p2，p1每次移动一步而p2每次移动2步，当p2达到尾部时p1大约位于链表中间点附近，这样做时间复杂度为O(N)；代码示意：
|
1
2
3
4
5
6 |
ListNode* p1 = head;ListNode* p2 = head;while
(p2!=NULL && p2->next!=NULL) { p1 = p1->next; p2 = p2->next->next;} |
3.一个算法如果对于顺序表需要进行复制，交换等操作的话，那么当该算法移植到链表上用时，尽可能将复制替换等操作改为连标间的指针重指向操作，尽可能不制造新的链表结点。
|
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
48
49 |
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class
Solution { ListNode *directInsert(ListNode* head) { if
(head == NULL || head->next==NULL) return
head; ListNode* dump = new
ListNode(0); dump->next = head; ListNode* p = head->next; ListNode* p_pre = head; ListNode* p_next = p->next; int
temp; int
mark = 0; while
(p != NULL) { mark = 0; p_next = p->next; //必须在交换发生前确定好下一个待插入元素的指针 temp = p->val; ListNode* q = dump->next; ListNode* q_pre = dump; while
(q != p) { if
(q->val > temp) { p_pre->next = p->next; //p父结点指向p的子结点 p->next = q; //p指向q q_pre->next = p; //q的父结点指向p mark = 1; break; //已找到插入位置并插入完毕，结束当前循环 } q_pre = q; q = q->next; } if
(mark == 0) p_pre = p_pre->next; //如果没有发生交换，则p_pre后移 p = p_next; } head = dump->next; delete
dump; return
head; } public: ListNode *insertionSortList(ListNode *head) { return
directInsert(head); }}; |
LeetCode: Insertion Sort List(外加对单链表类题目的思考总结),布布扣,bubuko.com
LeetCode: Insertion Sort List(外加对单链表类题目的思考总结)
原文：http://www.cnblogs.com/zanghu/p/3619141.html