[LeetCode]21. Merge Two Sorted lists

Merge Two Sorted Lists - LeetCode

두 리스트 list1, list2의 head를 받는다.

두 리스트를 하나의 정렬된 리스트로 병합해야한다.

• 순차적으로 비교해 나간다.
• 비교 후, 둘 중 하나의 리스트는 남아있는 값이 있을 수 있다. ( 둘 다 있을 수는 없다. 순차 비교를 했기 때문에 )
  • 남아있는 리스트 전체를 res에다가 덧붙여준다
• 이 경우 시간 복잡도는 → O(n)이 된다.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
				// 둘 중 하나의 리스트가 빈 리스트인 경우 
        if(list1 == null) return list2;
        else if ( list2 == null)return list1;
        ListNode res = new ListNode(0);
        // 결과를 리턴해야하기 때문에, 첫번째 노드를 기억하고 있어야함.
        // 따라서 덧붙이는 노드들은 모두, first.next 부터 시작해서 연결되는 것들
        ListNode first = res;
        // 두 리스트 안의 노드의 수는 0이상 50 이하다
        // res 가 아니라 res.next 에다가 위치시켜야 한다.
        while(list1!=null){
            while(list2 != null){
                // list1.val <= list2.val 이면 break -> one의 값을 res에 추가
                if(list1.val <= list2.val) break;
                // Otherwise , two의 값을 res에 추가
                res.next = new ListNode(list2.val);
                res = res.next;
                list2 = list2.next;
            }
            res.next = new ListNode(list1.val);
            res = res.next;
            list1 = list1.next;
        }
        // 끝나고 남은 것을 붙여준다
        if(list1 != null){
            res.next = list1;
        }else if(list2 != null){
            res.next = list2;
        }
        return first.next;
    }
}

• 여기서 dummy node 역할을 하는 것이 필요한 이유는, res에 요소를 덧붙이고 res를 업데이트 시키다 보면, 결국 이 연결리스트의 첫번째 요소를 가리키고 있는 헤더 역할을 하는애가 없어지기 때문이다.

파이썬

# 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]
        """
        # 둘 중 하나의 리스트가 비어있는 경우 -> 다른 리스트를 반환
        if list1 == None:
            return list2
        if list2 == None:
            return list1
        # 순차적으로 비교해 나간다 
        first = res = ListNode()
        while list1 != None:
            while list2 != None:
                # 현재 list1 요소 <= list2 요소  ===>  list1 요소를 res에 붙인다. 
                # Otherwise ===> list2 요소를 res에 붙인다 
                if list1.val <= list2.val:
                    break
                res.next =ListNode(list2.val)
                res = res.next
                list2 = list2.next
            res.next = ListNode(list1.val)
            res = res.next
            list1 = list1.next
        # 두 리스트 중 남아있는 부분을 res에 덧붙인다. 
        if list1 != None:
            res.next = list1
        if list2 != None:
            res.next = list2
        return first.next

위의 방식을 그대로 유지하고

• python에서는 “조건문”에 None이 오면 false임을 고려하면 아래와 같이 바꿀 수가 있다.

# 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]
        """
        # 둘 중 하나의 리스트가 비어있는 경우 -> 다른 리스트를 반환
        if list1 == None:
            return list2
        if list2 == None:
            return list1
        # 순차적으로 비교해 나간다 
        first = res = ListNode()
        while list1 and list2:
            if list1.val <= list2.val:
                res.next = ListNode(list1.val)
                list1 = list1.next
            else:
                res.next = ListNode(list2.val)
                list2 = list2.next
            res = res.next
            
        # 나머지 경우를 덧붙이기 위함 
        res.next = list1 or list2
        return first.next

여기서 이런식으로 하는 부분들이 상당히 생소하다..

        while list1 and list2:

        res.next = list1 or list2