Python으로 푸는 LeetCode 21. Merge Two Sorted Lists (Easy)

LeetCode 21. Merge Two Sorted Lists (Easy)

주어진 정렬된 2개의 Linked List의 Head를 가지고, 

두 List의 원소들을 작은 값부터 차례로 정렬된  List의 Head를 반환하시오.

LeetCode에서 푼 문제 리스트 보기

LeetCode에서 문제 보기

Github에서 코드 보기

문제 풀이

input에서 주어진 두 Linked List는 이미 정렬되어 있다. 따라서 각각의 head부터 순회하면서 작은값들을 가져와 Linked list를 새로 만들어주면 된다. 만약 두 List 중에 하나라도 빌 경우 나머지 Linked List를 현재의 node에다가 이어주기만 하면 된다.

파이썬 코드

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
 
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = None
        start = None
        while l1 and l2:
            next = None
            l1_v, l2_v  = l1.val, l2.val
 
            if l1_v <= l2_v:
                next = l1
                l1 = l1.next
            else:
                next = l2
                l2 = l2.next
 
            if start == None:
                start = ListNode(next.val)
                head = start
            else:
                start.next = ListNode(next.val)
                start = start.next
 
        if l1:
            if start:
                start.next = l1
            else:
                head = l1
 
        if l2:
            if start:
                start.next = l2
            else:
                head = l2
 
        return head
 
 
def printAll(head):
    start = head
    while start:
        print(start.val)
        start = start.next
 
 
if __name__ == "__main__":
    # 1->2->4, 1->3->4
    l1_1 = ListNode(1)
    l1_2 = ListNode(2)
    l1_3 = ListNode(4)
    l1_1.next = l1_2
    l1_2.next = l1_3
 
    l2_1 = ListNode(1)
    l2_2 = ListNode(3)
    l2_3 = ListNode(4)
    l2_1.next = l2_2
    l2_2.next = l2_3
 
    s = Solution()
    result = s.mergeTwoLists(l1_1, l2_1)
    printAll(result)