문제14: 두 정렬 리스트의 병합

문제

입력

1->2->4, 1->3->4

출력

1->1->2->3->4->4

풀이

1. 한 개의 포인터로 돌면서 조회 → O(n)

result = head = None

while list1 != None and list2 != None:
	if list1.val < list2.val:
		result.next = list1.copy()
		list1 = list1.next
	else:
		result.next = list2.copy()
		list2 = list2.next

	if result == None:
		head = result.next

	result = result.next

if list1 != None:
	result.next = list1
else:
	result.next = list2

return head

새로운 개념