[leetcode] 21. Merge Two Sorted Lists [easy]

# 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:
        
        ans = ListNode(None)
        temp = ans
        node1 = l1
        node2 = l2
        v1, v2 = -1, -1
        while node1 != None:
            
            # set values
            v1 = node1.val
            if node2 != None:
                v2 = node2.val
                if v1 <= v2:
                    temp.next = ListNode(v1)
                    node1 = node1.next
                else:
                    temp.next = ListNode(v2)
                    node2 = node2.next
            else:
                temp.next = ListNode(v1)
                node1 = node1.next
            
            temp = temp.next
            
        while node2 != None:
            v2 = node2.val
            temp.next = ListNode(v2)
            temp = temp.next
            node2 = node2.next

        return ans.next
        
        
        

 

[문제]

정렬된 2개의 linked list를 merge해서 하나의 linked list를 만든다.

Input: 1->2->4, 1->3->4

Output: 1->1->2->3->4->4

 

[풀이]

하나의 linked list를 기준점으로 잡고, loop를 돌면서 두 개 linked list 값들을 비교한다.

그 다음에는 나머지 linked list를 loop 돌면서 값들을 처리한다.

 

[더 심플한 풀이 방법]

# 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:
        ans = ListNode(None)
        cur = ans
        
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = ListNode(l1.val)
                l1 = l1.next
            else:
                cur.next = ListNode(l2.val)
                l2 = l2.next
            cur = cur.next
        
        if l1:
            # print('l1',l1)
            cur.next = l1
        if l2:
            # print('l2',l2)
            cur.next = l2
        
        return ans.next