[LeetCode] 21. Merge Two Sorted Lists

轉自LeetCode

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

<Solution>

這題就是 merge sort 的 merge，只是資料結構是 link list

邏輯都是一樣，注意 link list 的操作就好

code 如下
c++

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
	ListNode *head = new ListNode(0);
	ListNode *curr = head;
	while(l1 && l2) {
	if(l1->val < l2->val) {
	curr->next = l1;
	curr = l1;
	l1 = l1->next;
	}
	else {
	curr->next = l2;
	curr = l2;
	l2 = l2->next;
	}
	}
	if(l1) {
	curr->next = l1;
	}
	if(l2) {
	curr->next = l2;
	}
	return head->next;
	}
	};

view raw mergeTwoSortedLists.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 mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? {
	val pq = PriorityQueue() {v1: Int, v2: Int -> v1 - v2} //min heap
	var node = l1
	while(node != null) {
	pq.add(node!!.`val`)
	node = node?.next
	}
	node = l2
	while(node != null) {
	pq.add(node!!.`val`)
	node = node?.next
	}
	val dummyHead = ListNode(-1)
	var currentNode = dummyHead
	while(pq.isNotEmpty()) {
	val newNode = ListNode(pq.first())
	currentNode.next = newNode
	currentNode = currentNode.next
	pq.remove()
	}
	return dummyHead.next
	}
	}

view raw merge_two_sorted_lists.kt hosted with ❤ by GitHub