有点难的题目,因为没有想到归并排序的思想。简单来说就是不断的对半分割,然后递归的完成两个分块的排序之后,再将这两个排好序的分块按序合并,就完成了排序。先贴一种自顶向下的方法。这种方法的细节之处在于不断的分割过程中,对只剩两个元素的情况进行处理,删去第二个元素,也就是将头结点的next指针设为null。而这种方法的依据在于分割的过程中存在重复的元素,比如3个元素的单元会被分为两个2元素的单元,第一个单元继承原始单元的第一个元素,第二个则继承第二个,第三个不用管,因为这是分割前另外一块的开头。贴代码
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode() : val(0), next(nullptr) {} 7 * ListNode(int x) : val(x), next(nullptr) {} 8 * ListNode(int x, ListNode *next) : val(x), next(next) {} 9 * }; 10 */ 11 class Solution { 12 public: 13 ListNode* sortList(ListNode* head) 14 { 15 return sort(head,nullptr); 16 } 17 ListNode* sort(ListNode* head,ListNode* tail) 18 { 19 if(!head) 20 return nullptr; 21 // 22 if(head->next == tail) 23 { 24 head->next = nullptr; 25 return head; 26 } 27 //分 28 ListNode* pointer_1 = head; 29 ListNode* pointer_2 = head; 30 while(pointer_2!=tail) 31 { 32 pointer_1 = pointer_1->next; 33 pointer_2 = pointer_2->next; 34 if(pointer_2!=tail) 35 pointer_2 = pointer_2->next; 36 } 37 ListNode* mid = pointer_1; 38 //分割时存在重叠部分,而这一部分会在分割到两个元素时被舍去,很巧妙的设计 39 ListNode* head_1 = sort(head,mid); 40 ListNode* head_2 = sort(mid,tail); 41 return merge(head_1,head_2); 42 } 43 ListNode* merge(ListNode* head_1,ListNode* head_2) 44 { 45 ListNode* head = new ListNode(0); 46 ListNode* temp = head; 47 ListNode* temp_1 = head_1; 48 ListNode* temp_2 = head_2; 49 while(temp_1!=nullptr && temp_2!=nullptr) 50 { 51 if(temp_1->val > temp_2->val) 52 { 53 temp->next = temp_2; 54 temp_2 = temp_2->next; 55 } 56 else 57 { 58 temp->next = temp_1; 59 temp_1 = temp_1->next; 60 } 61 temp = temp->next; 62 } 63 if(temp_1) 64 temp->next = temp_1; 65 else if(temp_2) 66 temp->next = temp_2; 67 return head->next; 68 } 69 };
修改了下分割时无重叠的方法,几个小细节改一下,贴代码
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode() : val(0), next(nullptr) {} 7 * ListNode(int x) : val(x), next(nullptr) {} 8 * ListNode(int x, ListNode *next) : val(x), next(next) {} 9 * }; 10 */ 11 class Solution { 12 public: 13 ListNode* sortList(ListNode* head) 14 { 15 if(!head) 16 return head; 17 ListNode* end = head; 18 while(end->next) 19 end = end->next; 20 return sort(head,end); 21 } 22 ListNode* sort(ListNode* head,ListNode* tail) 23 { 24 if(head == nullptr) 25 return nullptr; 26 if(head == tail) 27 { 28 head->next = nullptr; 29 return head; 30 } 31 //分 32 ListNode* pointer_1 = head; 33 ListNode* pointer_2 = head; 34 while(pointer_2!=tail) 35 { 36 //由于分割时不存在重叠部分,于是只有在快指针能够推两次的情况下慢指针才会推一次 37 //为了两个元素时能够分割正确 38 pointer_2 = pointer_2->next; 39 if(pointer_2!=tail) 40 { 41 pointer_1 = pointer_1->next; 42 pointer_2 = pointer_2->next; 43 } 44 } 45 //cout<<pointer_1->next->val<<endl; 46 //cout<<pointer_2->val<<endl; 47 ListNode* mid = pointer_1->next; 48 //分割时不存在重叠部分 49 ListNode* head_1 = sort(head,pointer_1); 50 ListNode* head_2 = sort(mid,pointer_2); 51 //cout<<head_1->val<<endl; 52 return merge(head_1,head_2); 53 } 54 ListNode* merge(ListNode* head_1,ListNode* head_2) 55 { 56 ListNode* head = new ListNode(0); 57 ListNode* temp = head; 58 ListNode* temp_1 = head_1; 59 ListNode* temp_2 = head_2; 60 while(temp_1!=nullptr && temp_2!=nullptr) 61 { 62 if(temp_1->val > temp_2->val) 63 { 64 temp->next = temp_2; 65 temp_2 = temp_2->next; 66 } 67 else 68 { 69 temp->next = temp_1; 70 temp_1 = temp_1->next; 71 } 72 temp = temp->next; 73 //cout<<temp->val<<endl; 74 } 75 if(temp_1) 76 temp->next = temp_1; 77 else if(temp_2) 78 temp->next = temp_2; 79 return head->next; 80 } 81 };
除了上述的自顶向下的方法,还有自下向顶的方法,首选以每个节点为单位进行两个两个的排序,以这种方式完成第一轮排序之后,就进行循环,将上述的子串的大小加倍,将两个各自完成排序的子串进行归并排序,以此类推,能够完成整个串的排序。代码的撰写中细节主要在于找到两个子串的头以及将子串分隔开。尤其是第二个子串,可能会出现元素不足甚至就没有元素的情况,所以需要单独的取出进行讨论。
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode() : val(0), next(nullptr) {} 7 * ListNode(int x) : val(x), next(nullptr) {} 8 * ListNode(int x, ListNode *next) : val(x), next(next) {} 9 * }; 10 */ 11 class Solution { 12 public: 13 ListNode* sortList(ListNode* head) 14 { 15 if(!head) 16 return nullptr; 17 int length = 0; 18 ListNode* listSize = head; 19 while(listSize!=nullptr) 20 { 21 length++; 22 listSize = listSize->next; 23 } 24 //将newHead的next节点赋为head主要是为了之后的循环变量temp的使用 25 ListNode* newHead = new ListNode(0,head); 26 for(int subLength = 1 ; subLength < length ; subLength*=2) 27 { 28 ListNode* preHead = newHead; 29 ListNode* temp = newHead->next; 30 while(temp!=nullptr) 31 { 32 //找到第一个head 33 ListNode* head_1 = temp; 34 for(int i = 1 ; i < subLength && temp->next!=nullptr ; i++) 35 temp = temp->next; 36 ListNode* head_2 = temp->next; 37 temp->next = nullptr; 38 temp = head_2; 39 //找到第二个head 40 for(int i = 1 ; i < subLength && temp!=nullptr && temp->next!=nullptr ; i++) 41 temp = temp->next; 42 ListNode* end = nullptr; 43 //判断第二个部分中是否有元素,如果有,则将temp的next元素脱钩 44 //如果无元素,则无需脱钩 45 if(temp!=nullptr) 46 { 47 end = temp->next; 48 temp->next = nullptr; 49 } 50 //合并 51 ListNode* merged = merge(head_1,head_2); 52 preHead->next = merged; 53 while(preHead->next!=nullptr) 54 preHead = preHead->next; 55 temp = end; 56 } 57 } 58 return newHead->next; 59 } 60 ListNode* merge(ListNode* head_1,ListNode* head_2) 61 { 62 ListNode* head = new ListNode(0); 63 ListNode* temp = head; 64 ListNode* temp_1 = head_1; 65 ListNode* temp_2 = head_2; 66 while(temp_1!=nullptr && temp_2!=nullptr) 67 { 68 if(temp_1->val > temp_2->val) 69 { 70 temp->next = temp_2; 71 temp_2 = temp_2->next; 72 } 73 else 74 { 75 temp->next = temp_1; 76 temp_1 = temp_1->next; 77 } 78 temp = temp->next; 79 //cout<<temp->val<<endl; 80 } 81 if(temp_1) 82 temp->next = temp_1; 83 else if(temp_2) 84 temp->next = temp_2; 85 return head->next; 86 } 87 };