?LeetCode刷題實(shí)戰(zhàn)148：排序鏈表
Given the head of a linked list, return the list after sorting it in ascending order.
Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?
題意
解題
/**
?* Definition for singly-linked list.
?* struct ListNode {
?* int val;
?* ListNode *next;
?* ListNode(int x) : val(x), next(NULL) {}
?* };
?*/
class?Solution?{
public:
??ListNode* sortList(ListNode* head) {
????if?(head == NULL?|| head->next == NULL) {
??????return?head;
????}
????ListNode *end = head;//定位到鏈表的尾部
????while?(end != NULL?&& end->next != NULL) {
??????end = end->next;
????}
????return?mergeSort(head, end);
??}
??//歸并排序
??ListNode* mergeSort(ListNode* head, ListNode *end) {
????if?(head == end) {//這段鏈表只有一個(gè)節(jié)點(diǎn)
??????return?head;
????}
????if?(head->next == end) {//只有兩個(gè)節(jié)點(diǎn)
??????if?(head->val > end->val) {
????????int tempVaule = head->val;
????????head->val = end->val;
????????end->val = tempVaule;
??????}
??????return?head;
????}
????????//快慢指針，定位鏈表中間
????ListNode *slowPtr = head, *fastPtr = head;
????while?(fastPtr != end) {
??????slowPtr = slowPtr->next;//慢指針走一步
??????fastPtr = fastPtr->next;//快指針走兩步
??????if?(fastPtr != end) {
????????fastPtr = fastPtr->next;//快指針走兩步
??????}
????}
????????
????//第一步 遞歸，排序右半
????ListNode * rightList = mergeSort(slowPtr->next, end);
????slowPtr->next = NULL;//將左右兩部分切開
????//第二步 遞歸，排序左半
????ListNode * leftList = mergeSort(head, slowPtr);
????????
????//第三步 合并
????ListNode *pHead = NULL, *pEnd = NULL;//合并鏈表的頭、尾
????if?(rightList == NULL) {
??????return?leftList;
????}
????//初始化頭結(jié)點(diǎn)、尾節(jié)點(diǎn)
????if?(rightList->val > leftList->val) {
??????pEnd = pHead = leftList;
??????leftList = leftList->next;
????}
????else?{
??????pEnd = pHead = rightList;
??????rightList = rightList->next;
????}
????//合并，每次將較小值放入新鏈表
????while?(rightList && leftList) {
??????if?(rightList->val > leftList->val) {
????????pEnd->next = leftList;
????????pEnd = pEnd->next;
????????leftList = leftList->next;
??????}
??????else?{
????????pEnd->next = rightList;
????????pEnd = pEnd->next;
????????rightList = rightList->next;
??????}
????}
????//可能某個(gè)鏈表有剩余
????if?(rightList == NULL) {
??????pEnd->next = leftList;
????}
????else?{
??????pEnd->next = rightList;
????}
????return?pHead;
??}
};