LeetCode: Sort List

 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     //需要注意，链表版的merge()要充分发挥链表的特性，不需要想顺序表那样进行复制
11     //归并的基本思想是不断将两条待排序链上的结点依次"摘"下来，再重新链起来
12     ListNode* merge(ListNode *h1, ListNode *h2) {
13         ListNode* head = NULL;
14         if (h1 == NULL) return h2;
15         if (h2 == NULL) return h1;
16         if (h1->val < h2->val) {
17             head = h1;
18             h1 = h1->next;
19         }
20         else {
21             head=h2;
22             h2 = h2->next;
23         }
24         ListNode* p = head;
25         while(h1!=NULL && h2!=NULL) {
26             if (h1->val < h2->val) {
27                 p->next = h1;
28                 h1 = h1->next;
29             }
30             else {
31                 p->next = h2;
32                 h2 = h2->next;
33             }
34             p = p->next;
35         }
36         if (h1 != NULL) p->next = h1;
37         else p->next = h2;
38         return head;
39     }
40     ListNode* mergesort(ListNode*head) {
41         if (head==NULL || head->next==NULL) return head; //链表mergesort的递归返回条件
42         ListNode* p1 = head;
43         ListNode* p2 = head;
44         ListNode* pre = NULL; //初值设为NULL或者p1
45         while (p2!=NULL && p2->next!=NULL) { //循环中p2只是个终止条件，之后不会用到
46             pre = p1;
47             p1 = p1->next;
48             p2 = p2->next->next;
49         }
50         pre->next = NULL; //打开链!
51         ListNode* h1 = mergesort(head);
52         ListNode* h2 = mergesort(p1);
53         return merge(h1, h2); //返回内容!!
54     }
55 
56 public:
57     ListNode *sortList(ListNode *head) {
58         return mergesort(head);
59     }
60 };