[LeetCode] 148. Sort List

轉自LeetCode

Sort a linked list in O(n log n) time using constant space complexity.
<Solution>
題目要求要 O(nlogn) 的時間複雜度，在這邊選擇用 merge sort

code 如下
c++

	/**
	* 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) {
	//>> merge sort
	return mergeSort(head);
	}
	ListNode *mergeSort(ListNode *node) {
	if(!node || !node->next) {
	return node;
	}
	//>> split
	ListNode *slow = node;
	ListNode *fast = node;
	while(fast->next && fast->next->next) {
	slow = slow->next;
	fast = fast->next->next;
	}
	ListNode *mid = slow->next;
	slow->next = NULL;
	//>> merge
	ListNode *leftHead = mergeSort(node);
	ListNode *rightHead = mergeSort(mid);
	ListNode *dummyHead = new ListNode(-1);
	ListNode *curNode = dummyHead;
	while(leftHead && rightHead) {
	if(leftHead->val < rightHead->val) {
	curNode->next = leftHead;
	leftHead = leftHead->next;
	}
	else {
	curNode->next = rightHead;
	rightHead = rightHead->next;
	}
	curNode = curNode->next;
	}
	if(!leftHead) {
	curNode->next = rightHead;
	}
	else {
	curNode->next = leftHead;
	}
	return dummyHead->next;
	}
	};

view raw mergeSortLinkedList_1.cpp hosted with ❤ by GitHub

或者使用 min heap 也是可以

kotlin

	/**
	* Example:
	* var li = ListNode(5)
	* var v = li.`val`
	* Definition for singly-linked list.
	* class ListNode(var `val`: Int) {
	* var next: ListNode? = null
	* }
	*/
	class Solution {
	fun sortList(head: ListNode?): ListNode? {
	val pq = PriorityQueue { n1: ListNode, n2: ListNode -> n1.`val` - n2.`val`} // min heap
	var currNode = head
	while(currNode != null) {
	pq.add(currNode!!)
	currNode = currNode?.next
	}
	val dummyHead = ListNode(0)
	currNode = dummyHead
	while(pq.isNotEmpty()) {
	currNode?.next = pq.first()
	pq.remove()
	currNode = currNode?.next
	}
	currNode?.next = null
	return dummyHead.next
	}
	}

view raw sort_list.kt hosted with ❤ by GitHub