leetcode#21 Merge Two Sorted Lists

1. 문제

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

2. 나의 풀이

2-1. while문으로 구현

# Definition for singly-linked list.

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        list1_head = list1
        list2_head = list2
        head = None
        current_cursor = None
        
        while True:
            # if current_cursor:
            #     print("!!current_cursor.val", current_cursor.val)
                
            if list1_head and list2_head:
                print(">>>", list1_head.val, list2_head.val)
                if list1_head.val <= list2_head.val:
                    if head:
                        current_cursor.next = ListNode(list1_head.val, None)
                        current_cursor = current_cursor.next
                    else:
                        head = ListNode(list1_head.val, None)
                        current_cursor = head
                    list1_head = list1_head.next
                else:
                    if head:
                        current_cursor.next = ListNode(list2_head.val, None)
                        current_cursor = current_cursor.next
                    else:
                        head = ListNode(list2_head.val, None)
                        current_cursor = head
                    list2_head = list2_head.next
                    
                # current_cursor = current_cursor.next
                continue
            if list1_head:
                # print(">>>", list1_head.val, "null")
                if head:
                    current_cursor.next = ListNode(list1_head.val, None)
                    current_cursor = current_cursor.next
                else:
                    head = ListNode(list1_head.val, None)
                    current_cursor = head
                
                list1_head = list1_head.next
                # current_cursor = current_cursor.next
                continue
            if list2_head:
                # print(">>>", "null", list2_head.val)
                if head:
                    current_cursor.next = ListNode(list2_head.val, None)
                    current_cursor = current_cursor.next
                else:
                    head = ListNode(list2_head.val, None)
                    current_cursor = head
                
                list2_head = list2_head.next
                # current_cursor = current_cursor.next
                continue
            return head

2-2. divide and conquer 적용

# Definition for singly-linked list.

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        
class Solution(object):
    def compareTwoNodes(self, node1, node2):
        if not node1 and node2:
            return node1, node2.next, ListNode(node2.val, None)
        if node1 and not node2:
            return node1.next, node2, ListNode(node1.val, None)
        if node1.val < node2.val:
            return node1.next, node2, ListNode(node1.val, None)

        return node1, node2.next, ListNode(node2.val, None)
            
    def __divideAndConquer(self, head, tail, node1, node2):
        if not node1 and not node2:
            return head
        if not head:
            new_node1, new_node2, tail = self.compareTwoNodes(node1, node2)
            head = tail
            return self.__divideAndConquer(head, tail, new_node1, new_node2)
        new_node1, new_node2, new_tail = self.compareTwoNodes(node1, node2)
        tail.next = new_tail
        return self.__divideAndConquer(head, new_tail, new_node1, new_node2)
    
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        head = None
        tail = None
        
        return self.__divideAndConquer(head, tail, list1, list2)

3. 남의 풀이

3-1. for문으로 해결

• https://velog.io/@kgh732/Python-%EC%9C%BC%EB%A1%9C-%ED%91%B8%EB%8A%94-Leetcode21.-Merge-Two-Sorted-Lists

# 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, list2):
        head = ListNode(-1)
        cursor = head
        
        while list1 != None and list2 != None:
            if list1.val <= list2.val:
                cursor.next = list1 # Update next node
                list1 = list1.next # Update l1
            else:
                cursor.next = list2 #Update next node
                list2 = list2.next # Updata l2
            
            cursor=cursor.next #Move cursor
        
        # Last node  
        if list1 != None:
            cursor.next = list1
        else:
            cursor.next = list2
            
        return head.next

Reference