Leetcode 148. 排序链表 解题思路及C++实现

解题思路：

对链表进行归并排序，使用 fast 和 slow 两个指针，遍历一次链表，就能将链表切分为两半，然后使用归并排序的方法。

 

/** * 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* fast = head; ListNode* slow = head; while(slow->next != NULL && fast->next != NULL && fast->next->next != NULL){ fast = fast->next->next; slow = slow->next; } ListNode* last = slow->next; slow->next = NULL; //切断成两个链表 //对两个链表递归做排序 ListNode* pre = sortList(head); ListNode* las = sortList(last); //对排好序的两个链表进行合并 return merge(pre, las); } ListNode* merge(ListNode* l1, ListNode* l2){ ListNode* tmp = new ListNode(0); ListNode* root = tmp; while(l1 != NULL && l2 != NULL){ if(l1->val > l2->val){ tmp->next = l2; l2 = l2->next; tmp = tmp->next; } else{ tmp->next = l1; l1 = l1->next; tmp = tmp->next; } } //对某一个链表中多出来的数，直接接在tmp后面 if(l2 == NULL) tmp->next = l1; if(l1 == NULL) tmp->next = l2; return root->next; } };