Leet Code - 21. Merge Two Sorted Lists(C++)

madpotato1713·2020년 1월 1일
0

알고리즘

목록 보기
16/76

예제: Merge Two Sorted Lists

문제
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.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

풀이

포인터를 사용하는 기본 문제이다.
기본 문제이지만.. 필자는 포인터를 대부분 잊어버렸기 때문에 꽤 성가신 문제였다.

기억을 더듬어 더듬어 풀었더니 다른 사람들의 풀이와 매우 비슷한 풀이가 나왔다. 기본 문제일수록 사람들의 생각이 다 비슷한가보다.

어쨌든, 이 문제 풀이에서 주요한 점은 head와 pt이다.
head와 pt가 가리키는 위치가 어디인지 잘 생각하면서 풀었다.

다음은 전체적인 소스코드이다.

소스 코드

class Solution {
public:
	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

		ListNode* head = new ListNode(0);
		ListNode* pt = head;

		while (l1 != NULL && l2 != NULL) {
			if (l1->val <= l2->val) {
				pt->next = l1;
				l1 = l1->next;
			}
			else {
				pt->next = l2;
				l2 = l2->next;
			}
			pt = pt->next;
		}

		if (l1 != NULL) {
			pt->next = l1;
		}
		else if (l2 != NULL) {
			pt->next = l2;
		}

		return head->next;
	}
};

풀이 후기

Your runtime beats 98.85 % of cpp submissions.
Your memory usage beats 86.07 % of cpp submissions.

풀이 결과다. 모자란 %는 어떻게 채울 수 있을까..

profile
개발자 성장일기

0개의 댓글