[코딩인터뷰] 연결리스트 - 두 정렬 리스트의 병합 문제풀이

문제

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

 

입력: l1 = [1 -> 2-> 4] / l2 = [1 -> 3-> 4]
출력 : [1 -> 1 -> 2 -> 3 -> 4 -> 4]

 

 

 

 

나의코드 (Fail)

# 정렬되어있는 두 연결 리스트를 합쳐라
# 입력 1->2->4, 1->3->4
# 출력 1->1->2->3->4->4

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


# 리스트 변환
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:

    while l1 is not None:
        prev = l1.val

        while l2 is not None:
            if prev >= l2.val:
                # l1이 기존에 가르키고있던 노드 저장
                prevL1 = l1.next

                # l1이 가리키는 노드를 l2로 변경
                l1.next = l2

                # 기존에 l2가 가리키던 노드를 저장
                prevL2 = l2.next

                # l2가 가리키는 노드를 l1 다음 노드로 변경
                l1.next.next = prevL1

                # l2는 기존 l2가 가리키던 노드로 변경
                l2 = prevL2
            else:
                # l2 다음 노드로 변경
                l2 = l2.next

        l1 = l1.next

    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)

resultNode = mergeTwoLists(l1, l2)

 

위 코드로는 해당 문제를 해결하지 못한다. 나는 l1의 노드를 차례대로 탐색하고, l2의 노드와 비교하여 작은 값을 가진 노드가 있으면 연결리스트의 next를 조정하는 방법으로 풀기 시작했다. 하지만 l2 While문을 타게되면 l2는 None 값이 되어버린다. 연결리스트는 반복문으로 해결하려고 하면 .next를 호출해서 탐색하기 때문에 마지막엔 None이 되는 것을 피해야한다는 것을 깨달았다. l2를 다른 변수에 담아서 체크 하기에는 l1으로 넘어갈 노드를 계속해서 체크해줘야하는 불편함이 있다.

 

 

 

 

정답코드

# Definition for singly-linked list.
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

출처 : github.com/onlybooks/algorithm-interview/blob/master/3-linear-data-structures/ch08/14-1.py

 

 

 

 

 

문제풀이

1) 설명

해당 문제는 재귀함수로 해결이 가능한 문제였다. 

if (not l1) or (l2 and l1.val > l2.val):
	l1, l2 = l2, l1

 

우선 연결리스트에서 위와 같이 노드를 바꾸면 어떤 현상이 일어날지를 알 수 있어야한다.

 

[l1]

1

2

4

[l2]

1

3

4

 

 

2) 과정

l1.val = 2, l2.val = 1일 경우

 

[l1]

1

1

3

4

[l2]

2

4

 

l1.val = 3, l2.val = 2일 경우

 

[l1]

1

1

2

4

[l2]

3

4

 

l1.val = 4, l2.val = 3일 경우

 

[l1]

1

1

2

3

4

[l2]

4

 

l1.val = 4, l2.val = 4일 경우

 

[l1]

1

1

2

3

4

[l2]

4

 

l1.val = None, l2.val = 4일 경우

 

[l1]

1

1

2

3

4

4

[l2]

None

 

 

 

 

정리

연결리스트에서 노드간의 swap 코드가 어떻게 연결리스트가 변화할지를 잘 이해하고 떠올려야한다. l1, l2 노드가 swap 되면서 l1와 연결되었던 next 노드들과 l2와 연결되었던 next 노드들이 한번에 바뀐다는 사실을 정리하고 넘어가자.