[leetcode]Sort List
题目要求：
Sort a linked list in O(n log n) time using constant space complexity.
数据结构定义：
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 */
这里用的数据结构是单链表。时间复杂度是O(n log n)的排序算法有：堆排序，快速排序，归并排序。题目要求使用常量的空间复杂度，这三种排序方法的空间复杂度分别是O(n),O(1),O(n)[对于数组]。归并排序的空间复杂度是O(n)，因为对于数组，归并排序需要额外的O(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 == NULL) 13 return head; 14 else if (head->next == NULL) 15 return head; 16 17 ListNode *slow = head, *fast = head; 18 while (fast->next != NULL && fast->next->next != NULL) 19 { 20 slow = slow->next; 21 fast = fast->next->next; 22 } 23 24 fast = slow; 25 slow = slow->next; 26 fast->next = NULL; 27 28 fast = sortList(head); 29 slow = sortList(slow); 30 31 return mergeList(fast,slow); 32 33 } 34 ListNode* mergeList(ListNode* list1Head, ListNode* list2Head){ 35 if (list1Head == NULL) return list2Head; 36 if (list2Head == NULL) return list1Head; 37 38 ListNode* result, *temp; 39 // initialize the first node of the merged result list 40 if (list1Head->val < list2Head->val){ 41 result = list1Head; 42 list1Head = list1Head->next; 43 } 44 else 45 { 46 result = list2Head; 47 list2Head = list2Head->next; 48 } 49 // operate the result list with temp 50 temp = result; 51 // end merge if at least one of the two lists reaches the tail node 52 while (list1Head != NULL && list2Head != NULL){ 53 if (list1Head->val < list2Head->val){ 54 temp->next = list1Head; 55 list1Head = list1Head->next; 56 } 57 else{ 58 temp->next = list2Head; 59 list2Head = list2Head->next; 60 } 61 temp = temp->next; 62 } 63 64 if (list1Head != NULL) 65 temp->next = list1Head; 66 else 67 temp->next = list2Head; 68 69 return result; 70 } 71 };
这个简单的OJ浪费了我大概半个多小时在调试BUG，实在有点太菜了。AC之前我的代码遇到了下面几个恶心的BUG。
1. 在找到链表的中间节点后，用head和slow来表示左右两个子脸变的时候，没有把中间节点的next指针置为空，导致程序无限递归，最后导致堆溢出。
2. 在合并排序数组的函数中，处理未添加到result链表中的节点（64~67）时，if语句条件写错了。....
.....
沉心学习，努力积累，希求爆发。
ionic介绍
ionic介绍
Ionic是一个前端的框架，帮助开发者使用HTML5, CSS3和JavaScript做出原生应用。
The beautiful, open source front-end framework for developing hybrid mobile apps with HTML5。
有了ionic, 我们就可以使用HTML5、javascript(angular)和css（sass）开发android和ios应用。
Getting Started with Ionic
安装ionic
安装nodejs
nodejs近年来非常热门，安装nodejs是为了可以通过命令行工具安装Cordova和ionic
安装cordova和ionic
|
1
|
npm install -g cordova ionic |
在Mac中，需要加上sudo：
|
1
|
sudo npm install -g cordova ionic |
创建应用
ionic官网为开发者提供了多个开发模板，如：
空白模板（Black app）
|
1
|
ionic start myApp blank |
tabs模板
|
1
|
ionic start myApp tabs |
sidemenu模板
|
1
|
ionic start myApp sidemenu |
运行ionic应用
|
1
|
cd myApp |
|
1
|
ionic platform add ios |
|
1
|
ionic build ios |
|
1
|
ionic emulate ios |
编译和运行android应用方法类似。