• 歡迎fork and star：Nowcoder-Repository-github

148. Sort List

題目

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

解答Accept

• 實作之前看了思路，想想先就用遞歸實作
• 結果模仿别人寫都有5個bug,感覺沒有用心啊！！！

// Definition for singly - linked list.
struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};

// sort list
class Solution {
public:

	ListNode* findMiddle(ListNode* head)
	{
		ListNode* slow = head;
		ListNode* fast = head->next;
		while (fast&&fast->next) //bug1 ||
		{
			slow = slow->next;
			fast = fast->next->next;
		}
		return slow;
	}

	ListNode* MergeList(ListNode* left, ListNode*right)
	{
		if (left==NULL)
		{
			return right;
		}
		if (right==NULL)
		{
			return left;
		}

		ListNode* temp = new ListNode(0);
		ListNode* temp_head = temp;  //bug2 頭指針移動
		while (left&&right)
		{
			if (left->val<right->val)
			{
				temp->next = left;  //bug3 順序反了
				left = left->next;
				
			}
			else
			{
				temp->next = right;
				right = right->next;
			}
			temp = temp->next;
		}

		if (left) //bug4 if->while
		{
			temp->next = left;
		}
		if (right)
		{
			temp->next = right;
		}

		return temp_head->next;

	}
	ListNode* sortList(ListNode* head) {

		if (!head||!head->next)  // Line 57: member access within null pointer of type 'struct ListNode'
		{
			return head;  //bug5 忘記取！
		}
		
		ListNode *middle = findMiddle(head);


		ListNode* left=sortList(middle->next);

		middle->next = NULL;
		ListNode* right = sortList(head);

		ListNode *ret=MergeList(left, right);
		return  ret;
	}
};

           

題目來源：148. Sort List，讨論裡面非遞歸實作

C/C++基本文法學習

STL

C++ primer