EEPW论坛

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

题意实现一个链表排序的算法;

方法一：刚开始想的是自己定义个比较函数，然后调用sort（）函数进行实现

1. class Solution  

2. {  

3. public:  

4.   

5.     static bool cmp(ListNode* a, ListNode* b)  

6.     {  

7.         return a->val < b->val;  

8.     }  

9.   

10.     ListNode* sortList(ListNode* head)  

11.     {  

12.         if (head==NULL)  

13.         {  

14.             return head;  

15.         }  

16.   

17.         vector<ListNode*> arrList;  

18.         ListNode* p = head;  

19.   

20.         while (p)  

21.         {  

22.             arrList.push_back(p);  

23.             p = p->next;  

24.         }  

25.   

26.         sort(arrList.begin(), arrList.end());  

27.   

28.         p = head = arrList[0];  

29.   

30.         for (int i=1; i<arrList.size(); i++)  

31.         {  

32.             p->next = arrList[i];  

33.             p = p->next;  

34.         }  

35.   

36.         arrList[arrList.size() - 1]->next = NULL;  

37.   

38.         return head;  

39.   

40.     }  

41. };  

方法二：因为题目要求的时间负责度O(nlogn), 故可以考虑归并排序的思想；

归并排序的一把步骤：

（1）将待排序数组去中间点并一分为二；

（2）递归地对左半部分进行归并排序；

（3）递归地对右半部分进行归并排序；

（4）将两个半部分进行合并，得到结果；

所以对应此题，可以分为三个小问题；

（1）找到链表中点；

（2）写出merge函数，即如何合并链表

（3）写出mergesort函数，实现上述步骤；

1. class Solution  

2. {  

3. public:  

4.   

5.     //找到链表中间位置  

6.     ListNode* findMid(ListNode* head)  

7.     {  

8.         ListNode* slow = head;  

9.         ListNode* fast = head;  

10.   

11.         while (fast!=NULL && fast->next!=NULL && fast->next->next!=NULL)  

12.         {  

13.             slow = slow->next;  

14.             fast = fast->next->next;  

15.         }  

16.   

17.         return slow;  

18.     }  

19.   

20.     //合并两个有序链表  

21.     ListNode* mergeList(ListNode* h1, ListNode* h2)  

22.     {  

23.         if (h1 == NULL)  

24.         {  

25.             return h2;  

26.         }  

27.         else if (h2 == NULL)  

28.         {  

29.             return h1;  

30.         }  

31.         else  

32.         {  

33.             ListNode* head = NULL;  

34.             if (h1->val>h2->val)  

35.             {  

36.                 head = h2;  

37.                 h2 = h2->next;  

38.             }  

39.             else  

40.             {  

41.                 head = h1;  

42.                 h1 = h1->next;  

43.             }  

44.   

45.             ListNode* p = head;  

46.             while (h1 && h2)  

47.             {  

48.                 if (h1->val < h2->val)  

49.                 {  

50.                     p->next = h1;  

51.                     h1 = h1->next;  

52.                 }  

53.                 else  

54.                 {  

55.                     p->next = h2;  

56.                     h2 = h2->next;  

57.                 }  

58.                 p = p->next;  

59.             }  

60.   

61.             if (h1) p->next = h1;  

62.             if (h2) p->next = h2;  

63.   

64.             return head;  

65.         }  

66.     }  

67.     ListNode* sortList(ListNode* head)  

68.     {  

69.         if (head == NULL || head->next == NULL)  

70.         {  

71.             return head;  

72.         }  

73.   

74.         ListNode* mid = findMid(head);  

75.   

76.         ListNode* h2 = sortList(mid->next);  

77.         mid->next = NULL;  

78.         ListNode* h1 = sortList(head);  

79.   

80.         return mergeList(h1, h2);  

81.     }  

82. };