Merge Two Sorted Lists - leetcode (21)

Merge Two Sorted Lists

요구사항

• You are given the heads of two sorted linked lists list1 and list2.
• Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
• Return the head of the merged linked list.
  => 두개의 정렬된 연결리스트 헤드가 제공되고, 두개의 노드를 하나의 정렬된 연결리스트로 만들고 병합된 연결리스트의 헤드를 반환한다.
  

Solution

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

l1 = ListNode(1)
l1.next = ListNode(2)
l1.next.next = ListNode(4)

l2 = ListNode(1)
l2.next = ListNode(3)
l2.next.next = ListNode(4)

class Solution:
    def mergeTwoLists(self, list1, list2):
     	# dummy와 현재 head로 이용할 노드 2개를 만들어 두는게 핵심이다.
        curr = dummy = ListNode(0)
       
       # list가 둘다 있다면 더 적은 val를 기준으로 next를 옮겨 나간다.
        while list1 and list2:
            if list1.val < list2.val:
                curr.next = list1
                list1 = list1.next
            else:
                curr.next = list2
                list2 = list2.next
            curr = curr.next
            
        # 두개의 리스트중 하나가 먼저 None에 도달하기 때문에 while문이 종료된 뒤 아래와 같이 만든것이다.
        curr.next = list1 or list2
        
        # dummy.next는 병합된 연결 리스트의 head와 연결되어 있다.
        return dummy.next
        
sol = Solution()

print(sol.mergeTwoLists(l1, l2))

📌 코드 풀이

1. 답으로 반환하는 용도인 dummy(head)와 두개를 병합하며 이동할 curr(head) 두 가지를 선언하는게 핵심이다.
2. L1과 L2가 존재할때 까지 while문을 돌고 L1.val < L2.val을 이용하여 값이 낮은쪽의 조건문이 돌게만들어준다.
3. 값이 낮은쪽에서 curr.next = list로 값이 낮은쪽 리스트와 연결하고, 해당 list = list.next로 뒷칸으로 이동시키고 조건문이 종료되면 curr = curr.next로 연결된곳으로 이동한다.
4. 2~3번을 반복하면 하나의 리스트가 먼저 list.next=None으로 빠지기 때문에 와일문은 돌아가지 않게되는데 이때 curr.next = L1 or L2로 None이 아닌 리스트를 next로 연결시켜준다.
5. 모든 연결리스트가 정렬 + 연결 되었기 때문에 처음에 만들어준 dummy.next를 반환하게 되면 연결된 결과문을 답으로 반환할 수 있다.

1.

2.

3.

4.

5.

6.

7.

leetcode

https://leetcode.com/problems/merge-two-sorted-lists/