(간단한 코드)리트코드 21. Merge Two Sorted Lists

 

두개의 연결리스트를 크기 순서대로 연결하는 문제이다. 

 

이 문제는 다음과 같은 단계로 값을 찾아 나갈 것이다.

 

연결 리스트 문제를 풀다보면, 정말로 자주 나오는 변수 dummy가 있다.

dummy는 가짜의, 모조품 이라고 생각을 하면 되는데(바보라는 뜻도 있다)

연결 리스트는 다음 원소를 찾는 과정에서 엉뚱한 곳으로 가는 경향이 있어서, 항상 우리가 반환 하고자 하는 첫번째 부분의 주소를 저장하기 위해서 dummy를 사용한다.

 

우선 코드를 보면 다음과 같다. (정답이 아니라 이해를 하고 싶다면, 코드보다는 설명을 먼저 보는 것을 권장한다)

# 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: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0,None) #이건 위의 기본 값을 설정한 것이다.
        cur = dummy
        
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1
                cur = list1
                list1 = list1.next
            else:
                cur.next = list2
                cur = list2
                list2 = list2.next
            
        cur.next = list1 if list1 else list2
        return dummy.next #여기서 dummy는 0, 그리고 다음 값이 우리가 원하는 출발점이다.

 

맨 마지막에 return을 할때, dummy.next라고 했다. 기존의 dummy에는 0이라는 임의의 숫자를 우리가 정해주고, 그 다음에 연결 리스트를 차곡차곡 연결해주기 때문이다. 

 

그럼 왜 그냥 연결리스트의 처음 부분을 따로 저장하지 않나요?라는 의문이 떠오른다면, 이건 파이썬의 scope 혹은 namespace에 관한 개념과, 하드웨어적인 개념을 알아야 이해할 수 있다.

https://www.youtube.com/watch?v=5xXB93rX_X8

위의 링크는 4시간 짜리 긴 강의 영상이지만, 정말로 잘 설명을 해주셨고, 친절하게 단락별로 타임라인도 정리가 되어있다.

다만 나는 이를 이해하기 위해서 우선적으로 하드웨어의 메모리 레지스터에 관한 부분을 머리 깨지면서 며칠동안 공부한 후에 겨우 받아들였다.

------------------------------------------------------------------------

 

코드에서 cur = list1, list1 = list1.next 이런 코드를 실제로 손으로 그려보려고 하다보면, 뭔가 이상해짐을 알 수 있다.

우선 연결리스트에서 주의해야 하는 점이 하나 있다. 그것은 연결리스트를 어떤 관점으로 바라 볼 것인지 이다.

리트코드 문제에서도 자주 등장하는 이런 형식으로 연결리스트를 받아들이는 것은 그다지 바람직하지 못하다.

 

연결이 간단하게 되어 있는 나머지, 모든 그림을 그리려고 노력하게 되기 때문이다.

 

나는 다음과 같이 연결리스트를 바라봤으면 한다.

 

RPG게임에 나오는 마을간의 이동 "지도"를 바라보는 것처럼. 

1번째 마을에 도착하면, 다음 행선지로 2번 마을을 안내하는 것처럼

 

전체적인 그림이 아니라 "마을 한개"만 바라보는 관점이 필요하다.

예를 들면 3번 마을이 어디있는지는 중요하지 않다, 다만 2번 마을에서 3번 마을에 대한 정보를 얻을 수 있다는 것을 알기만 하면 된다.

 

이는 처음에는 받아들이기 어려운 개념이다. 정확히는 낮선개념이다. 따라서 여러번 보는 것이 중요하다.