LeetCode) 21. Merge Two Sorted Lists

두 정렬 리스트의 병합

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

Merge Two Sorted Lists - LeetCode

 

 

linked list.. 개념은 익숙하나 처음 들어보는 자료구조다.

노드 관련해서는 많이 취약한 편이라 이번 자료구조는 풀기 어려웠다.

 

 

어찌저찌 통과는 했지만 답안을 보니 내가 푼것은 편법이였다.

두 배열의 값을 모두 꺼내 sort시킨 후 다시 노드로 만들어서 넣었다.

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

    def append(self, val):
        if self.head is None:
            self.head = ListNode(val)
            return

        nodel = self.head
        while nodel.next:
            nodel = nodel.next
        nodel.next = ListNode(val)
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:

        t1 = []
        t2 = []
        while list1:
            t1.append(list1.val)
            list1 = list1.next

        while list2:
            t2.append(list2.val)
            list2 = list2.next

        tl1 = t1 + t2
        tl1.sort(reverse=True)

        ans = LinkedList()
        for i in range(len(tl1) - 1, -1, -1):
            ans.append(tl1[i])

        return ans.head

 

 

답안은 정렬된 두 배열이라는 점을 활용해서 오직 주소 값만 변경해 문제를 풀었다. 하지만 이상하게도 실행시간이 더 오래 걸렸다. 

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

    def append(self, val):
        if self.head is None:
            self.head = ListNode(val)
            return

        nodel = self.head
        while nodel.next:
            nodel = nodel.next
        nodel.next = ListNode(val)


class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:

        if list1 is None:
            return list2
        if list2 is None:
            return list1

        ans = LinkedList()

        while list1 or list2:
            if list1 and list2 is None:
                ans.append(list1.val)
                list1 = list1.next
                continue
            elif list2 and list1 is None:
                ans.append(list2.val)
                list2 = list2.next
                continue

            if list1.val > list2.val:
                ans.append(list2.val)
                list2 = list2.next
            else:
                ans.append(list1.val)
                list1 = list1.next

        return ans.head

 

 

답안의 코드이다. 실행속도가 가장빠르지만 직관적으로 이해하기 힘들다.

메모리를 추가로 할당하지 않고 list1을 그대로 출력하는 모습이 인상적이다.

첫 번째 if문을 정리해 보겠다.

1. list1이 빈 배열이다.

2. list2에 값이 있고  list1의 값(첫번째 인덱스)이 list2보다 크다.

위 조건에 부합한다면 list1과 list2를 스왑한다.

그리고 list1의 다음 주소 부분에 재귀함수를 호출해 값을 채워 넣는다.

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if (not list1) or (list2 and list1.val > list2.val):
            list1, list2 = list2, list1
        if list1:
            list1.next = self.mergeTwoLists(list1.next, list2)

        return list1

 

 

답안 부분의 코드는 정말 창의적이여서 내가 따라할 수 있을것이라는 생각은 잘 안든다ㅠ