Code & Func

今天中午在Lintcode上刷了一道题——链表排序

题目很短：

在 O(n log n) 时间复杂度和常数级的空间复杂度下给链表排序。

最近几天也在做排序算法的实验，所以看到这道题想刷一下。

从题目的要求我们可以大概的想出几种能达到要求的排序：

快速排序
归并排序

这里是归并排序的实现：

归并排序的大概思路是：

在待排序列中找到中间元素，将待排序列分成两个待排序列，分别对这两个待排序列递归地调用归并排序，当待排序列中元素只剩一个时，序列显然有序。

现在只需要将两个有序序列合并成一个有序序列。

实现：

1
class ListNode {
2
public:
3
  int val;
4
  ListNode* next;
5
  ListNode(int v):val(v),next(nullptr){}
6
}
7

8
ListNode * sortList(ListNode * head) {
9
  // write your code here
10
  if (!head || !head->next) return head;
11

12

13
  ListNode *fast,*slow;
14
  fast = slow = head;
15
  while(fast->next != nullptr && fast->next->next != nullptr) {
34 collapsed lines
16
    fast = fast->next->next;
17
    slow = slow->next;
18
  }
19
  fast = slow;
20
  slow = slow->next;
21
  fast->next = nullptr;
22
  fast = sortList(head);
23
  slow = sortList(slow);
24
  return mergeList(fast,slow);
25

26
}
27

28
ListNode *mergeList(ListNode *l1,ListNode *l2){
29
  if (!l1) return l2;
30
  else if (!l2) return l1;
31

32
  ListNode* ret = new ListNode(0);
33
  ListNode*p = ret;
34
  while(l1 && l2) {
35
    if (l1->val > l2->val) {
36
      ret->next = l2;
37
      ret = ret->next;
38
      l2 = l2->next;
39
    } else {
40
      ret->next = l1;
41
      ret = ret->next;
42
      l1 = l1->next;
43
    }
44
  }
45
  ret->next = (l1)?l1:l2;
46
  ret = p->next;
47
  delete p;
48
  return ret;
49
}

这里的难点就是找出中间元素，将一个序列分成两个序列，这里的实现是快慢指针来实现的，即：

1
ListNode *fast,*slow;
2
fast = slow = head;
3
while(fast->next != nullptr && fast->next->next != nullptr) {
4
  fast = fast->next->next;
5
  slow = slow->next;
6
}