Sort List

Sort a linked list in O(n log n) time using constant space complexity.

这题要求我们对链表进行排序，我们可以使用divide and conquer的方式，依次递归的对链表左右两半进行排序就可以了。代码如下：

  1. class Solution {
  2. public:
  3.    ListNode *sortList(ListNode *head) {
  4.         if(head == NULL || head->next == NULL) {
  5.             return head;
  6.         }
  8.         ListNode* fast = head;
  9.         ListNode* slow = head;
  11.         //快慢指针得到中间点
  12.         while(fast->next && fast->next->next) {
  13.             fast = fast->next->next;
  14.             slow = slow->next;
  15.         }
  17.         //将链表拆成两半
  18.         fast = slow->next;
  19.         slow->next = NULL;
  21.         //左右两半分别排序
  22.         ListNode* p1 = sortList(head);
  23.         ListNode* p2 = sortList(fast);
  25.         //合并
  26.         return merge(p1, p2);
  27.     }
  29.     ListNode *merge(ListNode* l1, ListNode* l2) {
  30.         if(!l1) {
  31.             return l2;
  32.         } else if (!l2) {
  33.             return l1;
  34.         } else if (!l1 && !l2) {
  35.             return NULL;
  36.         }
  38.         ListNode dummy(0);
  39.         ListNode* p = &dummy;
  41.         while(l1 && l2) {
  42.             if(l1->val < l2->val) {
  43.                 p->next = l1;
  44.                 l1 = l1->next;
  45.             } else {
  46.                 p->next = l2;
  47.                 l2 = l2->next;
  48.             }
  50.             p = p->next;
  51.         }
  53.         if(l1) {
  54.             p->next = l1;
  55.         } else if(l2){
  56.             p->next = l2;
  57.         }
  59.         return dummy.next;
  60.     }
  61. };

Insertion Sort List

Sort a linked list using insertion sort.

这题要求我们使用插入排序的方式对链表进行排序，假设一个链表前n个节点是有序，第n + 1的节点需要遍历前n个，插入到合适位置就可以了。

代码如下：

  1. class Solution {
  2. public:
  3.      ListNode *insertionSortList(ListNode *head) {
  4.         if(head == NULL || head->next == NULL) {
  5.             return head;
  6.         }
  8.         ListNode dummy(0);
  10.         ListNode* p = &dummy;
  12.         ListNode* cur = head;
  13.         while(cur) {
  14.             p = &dummy;
  16.             while(p->next && p->next->val <= cur->val) {
  17.                 p = p->next;
  18.             }
  20.             ListNode* n = p->next;
  21.             p->next = cur;
  23.             cur = cur->next;
  24.             p->next->next = n;
  25.         }
  27.         return dummy.next;
  28.     }
  29. };