[Python] MergeTwoSortedLists

Easy난이도 Acceptence 56.6%의 문제

 

이문제는 2개의 정렬된 리스트 노드를 하나의 리스트노드로 정렬하여 반환하는 문제이다.

 

단순히 둘중하나가 None이면 남은 노드만 처리해주도록 추가하였고

둘다 있을경우 값을 비교하여 output을 만들어 내었다.

 

dummy 노드를 만들어 output에 얕은 복사후 반환하면 reverse함수를 사용하지 않아도 되지만

이번 문제에선 정답으로 만든 output이 tail을 가리키고 있기 때문에 역으로 만들어 반환하였다.

 

class Solution(object):
    def __init__(self):
        self.output = None

    # 검증은 했지만 정확한 원리파악이 필요
    def reverse(self):
        prev = None
        cur = self.output
        while cur != None:
            nextNode = cur.next
            cur.next = prev
            prev = cur
            cur = nextNode
        self.output = prev

    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        while l1 != None or l2 != None:
            if l2 == None:
                self.output = ListNode(l1.val, self.output)
                l1 = l1.next
                continue
            if l1 == None:
                self.output = ListNode(l2.val, self.output)
                l2 = l2.next
                continue

            if l1.val <= l2.val:
                self.output = ListNode(l1.val, self.output)
                l1 = l1.next
            else:
                self.output = ListNode(l2.val, self.output)
                l2 = l2.next

        self.reverse()
        return self.output