LeetCode 148:Sort List

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

//題目要求：對鏈表進行排序
//解題思路：歸並排序，再Merge
//歸並排序的基本思想是：找到鏈表的中間節點，然後遞歸對前半部分和後半部分分別進行歸並排序，最後對兩個排好序的鏈表進行Merge
 class Solution {
 public:
	 ListNode* sortList(ListNode* head) {
		 if (head == NULL || head->next == NULL)  return head;

		 //快慢指針找到中間節點
		 ListNode *fast = head, *slow = head;
		 while (fast->next != NULL && fast->next->next != NULL)
		 {
			 fast = fast->next->next;
			 slow = slow->next;
		 }
		 //斷開
		 fast = slow;
		 slow = slow->next;
		 fast->next = NULL;

		 ListNode *l1 = sortList(head); //前半段排序
		 ListNode *l2 = sortList(slow); //後半段排序
		 return mergeTwoLists(l1, l2);
	 }

	 //Merge Two Sorted Lists
	 ListNode *mergeTwoLists(ListNode *l1, ListNode *l2){
		 ListNode dummy(-1);
		 for (ListNode* p = &dummy; l1 != NULL || l2 != NULL; p = p->next)
		 {
			 int val1 = l1 == NULL ? INT_MAX : l1->val;
			 int val2 = l2 == NULL ? INT_MAX : l2->val;
			 if (val1 <= val2)
			 {
				 p->next = l1;
				 l1 = l1->next;
			 }
			 else
			 {
				 p->next = l2;
				 l2 = l2->next;
			 }
		 }
		 return dummy.next;
	 }
 };