Sort List & Insertion Sort List

148. Sort List

题目链接：https://leetcode.com/problems/sort-list/#/description

题目大意：给定一个链表，要求以O(nlogn)时间复杂度和O(1)空间复杂度将链表排序。

思路：使用归并排序

算法步骤：（1）使用快慢指针将链表分为两部分，如果链表长度小于2，则不划分，直接返回链表；（2）将得到的两个链表分别排序；（3）合并两个有序链表。

算法复杂度：时间复杂度O(nlog(n))，空间复杂度O(1)

代码：

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* sortList(ListNode* head) {
12         if (!head || !head->next)
13             return head;
14         ListNode *fast = head, *slow = head;
15         while (fast->next && fast->next->next) {
16             fast = fast->next->next;
17             slow = slow->next;
18         }
19         fast = slow->next;
20         slow->next = nullptr;
21         
22         ListNode *l1 = sortList(head);
23         ListNode *l2 = sortList(fast);
24         
25         return mergeList(l1, l2);
26     }
27     ListNode *mergeList(ListNode *l1, ListNode *l2) {
28         ListNode res(0), *pres = &res;
29         while (l1 && l2) {
30             if (l1->val <= l2->val) {
31                 pres->next = l1;
32                 l1 = l1->next;
33             }
34             else {
35                 pres->next = l2;
36                 l2 = l2->next;
37             }
38             pres = pres->next;
39         }
40         pres->next = l1 ? l1 : l2;
41         return res.next;
42     }
43 };

评测系统上运行结果：

147. Insertion Sort List

题目链接：https://leetcode.com/problems/insertion-sort-list/#/description

题目大意：给定一个链表，使用插入排序算法对链表进行排序

算法步骤：（1）while循环找到插入点；（2）将当前节点插入插入点。

算法复杂度：时间复杂度O(n^2)，空间复杂度O(1)

代码：

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* insertionSortList(ListNode* head) {
12         if (!head || !head->next)
13             return head;
14         ListNode pstart(0), *pcurr = head->next, *ppre = head;
15         pstart.next = head;
16         while(pcurr) {
17             ListNode *p = &pstart;
18             while (p->next != pcurr && p->next->val <= pcurr->val)
19                     p = p->next;
20             if (p->next == pcurr) {
21                 ppre = ppre->next;
22                 pcurr = pcurr->next;
23             } else {
24                 ppre->next = pcurr->next;
25                 pcurr->next = p->next;
26                 p->next = pcurr;
27                 pcurr = ppre->next;
28             }
29         }
30         return pstart.next;
31     }
32 };

评测系统上运行结果：