두 list 를 합친다.

recursive

class Solution {
public:
	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
		if (l1 == NULL) return l2;
		else if (l2 == NULL) return l1;
		if (l1->val <= l2->val)
		{
			l1->next = mergeTwoLists(l1->next, l2);
			return l1;
		}
		else
		{
			l2->next = mergeTwoLists(l1, l2->next);
			return l2;
		}
	}
};

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Merge Two Sorted Lists.

Memory Usage: 14.7 MB, less than 87.01% of C++ online submissions for Merge Two Sorted Lists.

Runtime: 8 ms, faster than 81.85% of C++ online submissions for Merge Two Sorted Lists.

Memory Usage: 14.8 MB, less than 87.01% of C++ online submissions for Merge Two Sorted Lists.

iterative

class Solution {
public:
	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
		ListNode* dummyNode = new ListNode(-1);
		ListNode* curNode = dummyNode;
		while (l1 && l2)
		{
			if (l1->val <= l2->val)
			{
				curNode->next = l1;
				l1 = l1->next;
				curNode = curNode->next;
			}
			else // l2 가 더 클때
			{
				curNode->next = l2;
				l2 = l2->next;
				curNode = curNode->next;
			}
		}

		if (l2) curNode->next = l2;
		else curNode->next = l1;

		return dummyNode->next;
	}
};

Runtime: 4 ms, faster than 97.50% of C++ online submissions for Merge Two Sorted Lists.

Memory Usage: 14.7 MB, less than 87.01% of C++ online submissions for Merge Two Sorted Lists.

Runtime: 8 ms, faster than 81.85% of C++ online submissions for Merge Two Sorted Lists.

Memory Usage: 14.7 MB, less than 87.01% of C++ online submissions for Merge Two Sorted Lists.