Tuesday, December 3, 2013

[LeetCode] Sort List, Solution

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

[Thoughts]
O(nlgn)的排序算法没几个，无非就是quick sort， heap sort和merge sort. 对于链表排序来说，难点之一就是如何O(1)定位节点。如果是数组，那么可以通过下标直接找到节点，但是对于链表，很明显没有下标这个东西可以用，如果需要定位到第k个元素，只能从节点头部顺序的访问K次，但是，如果排序中每一个定位操作都要这样做的话，就太慢了。

[Code]

``````1:    ListNode *sortList(ListNode *head) {
2:      if(head == NULL) return NULL;
3:      int len = 0;
5:      while(it!= NULL)
6:      {
7:        len++;
8:        it = it->next;
9:      }
12:    }
13:    ListNode* Sort(ListNode````**```` head, int length)
14:    {
15:         if (length == 1)
16:         {
18:              ````*head = (*head)->next;````  // 确保head每被访问一次，则向后移动一次
19:              ````temp->next = NULL; // 尾节点需要为NULL，否则Merge函数没法使用````
20:              return temp;
21:         }
26:    }
27:    ListNode* Merge(ListNode* first, ListNode* second) // 普通的链表merge函数
28:    {
29:      ListNode* head = new ListNode(-1);
31:      while(first!=NULL || second!=NULL)
32:      {
33:        int fv = first == NULL? INT_MAX:first->val;
34:        int sv = second == NULL? INT_MAX:second->val;
35:        if(fv<=sv)
36:        {
37:          cur->next = first;
38:          first = first->next;
39:        }
40:        else
41:        {
42:          cur->next = second;
43:          second = second->next;
44:        }
45:        cur = cur->next;
46:      }
49:      return cur;
50:    }
``````

Update 08/23/2014
True. Recursion is not constant space. I didn't read the problem description carefully. Here, add an implementation via iteration.

Same idea as merge sort.  One example as below:

For each round, the iteration is O(n). And for merge sort, we totally need run the iteration for lg(n) round(the height of recursion tree). So, the total time complexity is  O(nlgn). Maybe someone can share a brief implementation. My current code is a bit fat.

``````1:  ListNode *sortList(ListNode *head) {
2:       // Get length first
4:       int len = 0;
5:       while (p != NULL)
6:       {
7:            p = p->next;
8:            len++;
9:       }
10:       ListNode* fakehead = new ListNode(-1);
12:       for (int interval = 1; interval <= len; interval = interval * 2)
13:       {
16:            while (fast != NULL || slow != NULL)
17:            {
18:                 int i = 0;
19:                 while (i< interval && fast != NULL)
20:                 {
21:                      fast = fast->next; //move fast pointer ahead 'interval' steps
22:                      i++;
23:                 }
24:                 //merge two lists, each has 'interval' length
25:                 int fvisit = 0, svisit = 0;
26:                 while (fvisit < interval && svisit<interval && fast != NULL && slow != NULL)
27:                 {
28:                      if (fast->val < slow->val)
29:                      {
30:                           pre->next = fast;
31:                           pre = fast;
32:                           fast = fast->next;
33:                           fvisit++;
34:                      }
35:                      else
36:                      {
37:                           pre->next = slow;
38:                           pre = slow;
39:                           slow = slow->next;
40:                           svisit++;
41:                      }
42:                 }
43:                 while (fvisit < interval && fast != NULL)
44:                 {
45:                      pre->next = fast;
46:                      pre = fast;
47:                      fast = fast->next;
48:                      fvisit++;
49:                 }
50:                 while (svisit < interval && slow != NULL)
51:                 {
52:                      pre->next = slow;
53:                      pre = slow;
54:                      slow = slow->next;
55:                      svisit++;
56:                 }
57:                 pre->next = fast;
58:                 slow = fast;
59:            }
60:       }
64:  }
``````