[Leetcode] 리트코드 - 두 정렬 리스트의 병합(merge-two-sorted-lists) 파이썬(python) 풀이

두 정렬 리스트의 병합

problem

문제링크

정렬되어 있는 두 연결 리스트를 합쳐라

입력 1→2→4 1→3→4
출력 1→1→2→3→4→4

solution

리트코드 정답

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if (not l1) or (l2 and l1.val > l2.val):
            l1, l2 = l2, l1
        if l1:
            l1.next = self.mergeTwoLists(l1.next, l2)
        return l1

풀이용 코드

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def my_print(l1: ListNode, l2:ListNode):

    print("l1 : ", end="")
    while l1 is not None:
        print(f'{l1.val} -> ', end="")
        l1 = l1.next
    print()

    print("l2 : ", end="")
    while l2 is not None:
        print(f'{l2.val} -> ', end="")
        l2 = l2.next
    print()


i = 0

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        global i
        i+=1
        print()
        print(f'{i}번째 mergeTowLists')


        if (not l1) or (l2 and l1.val > l2.val):
            print("첫번째 조건문")
            l1, l2 = l2, l1
            my_print(l1, l2)

        if l1:
            print("두번째 조건문")
            l1.next = self.mergeTwoLists(l1.next, l2)

        return l1


l1 = ListNode(1)
l1.next= ListNode(2)
l1.next.next = ListNode(4)

l2 = ListNode(1)
l2.next = ListNode(3)
l2.next.next = ListNode(4)

s = Solution()
answer = s.mergeTwoLists(l1, l2)
while answer is not None:
    print(f'{answer.val} ->', end=" ")
    answer = answer.next

첫번째 조건문은 l1에 객체가 없거나 l2에 객체가 존재하고, l1, l2노드를 비교했을 때 l1의 value가 더 컸을 때 실행된다. 두번째 조건문은 l1에 객체가 있을 때 실행된다.

풀이코드를 실행해서 재귀호출이 될 때마다 연결리스트를 위치를 확인해보면

1번째 mergeTowLists
두번째 조건문

2번째 mergeTowLists
첫번째 조건문
l1 : 1 -> 3 -> 4 ->
l2 : 2 -> 4 ->
두번째 조건문

3번째 mergeTowLists
첫번째 조건문
l1 : 2 -> 4 ->
l2 : 3 -> 4 ->
두번째 조건문

4번째 mergeTowLists
첫번째 조건문
l1 : 3 -> 4 ->
l2 : 4 ->
두번째 조건문

5번째 mergeTowLists
두번째 조건문

6번째 mergeTowLists
첫번째 조건문
l1 : 4 ->
l2 :
두번째 조건문

7번째 mergeTowLists
첫번째 조건문
l1 :
l2 :
1 -> 1 -> 2 -> 3 -> 4 -> 4 ->

이런식으로 연결리스트가 연결이 된다. 첫번째 mergeTwoLists와 두번째 mergeTwoLists는 두번째 조건문만 돌아가서 l1만 한칸옆으로 이동한 채 다음 mergeTwoLists를 호출하게 된다.

즉 그림으로 도식화를 했을 떄 밑의 과정으로 돌아간다.

출처
파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]