•
문제 설명 : 제공된 두 연결리스트를 합쳐서 반환한다.
•
풀이 방법
◦
총 3개의 커서를 사용하여 문제를 풀었다.
▪
각 연결리스트의 현재 노드를 가리키는 커서 1개씩
▪
전체 연결리스트의 현재 노드를 가리키는 커서 1개씩
•
시간복잡도 :
•
성공 코드
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
cursor1 = list1
cursor2 = list2
# 두 연결리스트 중 빈 연결리스트가 존재하는 경우 처리
if list1 == None and list2 == None:
return list1
elif list1 == None:
return list2
elif list2 == None:
return list1
# 연결된 연결리스트의 처리를 위한 커서 설정
if cursor1.val <= cursor2.val:
result_cursor = cursor1
cursor1 = cursor1.next
else:
result_cursor = cursor2
cursor2 = cursor2.next
# 한쪽의 연결리스트의 탐색이 끝날때까지 진행
while cursor1 != None and cursor2 != None:
# 더 작은쪽의 노드를 붙어준다
if cursor1.val <= cursor2.val:
result_cursor.next = cursor1
cursor1 = cursor1.next
else:
result_cursor.next = cursor2
cursor2 = cursor2.next
result_cursor = result_cursor.next
# 탐색이 끝나지 않은 나머지 노드를 연결한다.
# 탐색을 진행한 부분 이후는 전부 기존처럼 연결된 상태 그대로 사용하면 되기 때문에, 하나의 노드만 연결해준다.
if cursor1 == None:
result_cursor.next = cursor2
else:
result_cursor.next = cursor1
return list1 if list1.val <= list2.val else list2
Python
복사