https://leetcode.com/problems/merge-two-sorted-lists/
구현은 어렵지 않지만 LinkedList에 낯설면 접근하기 어려울 수도 있는 문제입니다.
두개의 정렬된 LinkedList가 주어지는데 이 둘을 합쳐 정렬된 하나의 LinkedList를 만들어야 합니다.
결과를 저장하기 위한 새로운 하나의 리스트를 만들고 입력된 두개의 리스트를 비교하면서 작은 순서대로 새로운 리스트에 붙여나갔습니다.
만약 입력 리스트 중에 하나가 끝난다면 결과 리스트의 맨 끝이 남은 입력리스트를 가리키게 하고 리턴했습니다.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
root = ListNode()
index = root
while(list1 and list2):
if(list1.val > list2.val):
index.next = list2
list2 = list2.next
index = index.next
else:
index.next = list1
list1 = list1.next
index = index.next
if(list1):
index.next = list1
elif(list2):
index.next = list2
return root.next
input = [[ListNode(1,ListNode(2, ListNode(4,None))),ListNode(1,ListNode(3, ListNode(4,None)))],
[None,None],
[None,ListNode(1,ListNode(3, ListNode(4,None)))],
[ListNode(1,None),None]]
for i in input:
answer = Solution().mergeTwoLists(i[0],i[1])
while(answer):
print(answer.val)
answer = answer.next
728x90
'🔍 알고리즘 > Leetcode' 카테고리의 다른 글
[Python] Leetcode 198. House Robber (Medium) (0) | 2022.07.23 |
---|---|
[Python] Leetcode 206. Reverse Linked List (Easy) (0) | 2022.07.23 |
[Python] Leetcode 746. Min Cost Climbing Stairs (Easy) (0) | 2022.07.22 |
[Python] Leetcode 70. Climbing Stairs (Easy) (0) | 2022.07.22 |
[Python] Leetcode 1137. N-th Tribonacci Number(Easy) (0) | 2022.07.22 |