8장_14 연결 리스트(두 정렬 리스트의 병합)


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

1. 재귀 구조로 연결

책의 문제 설명이랑 영상을 한참 보고도 90%는 이해했는데 혼자 다시 해보면 또 헷갈렸던 문제다.
코드는 무척이나 간단한데 그 안에서 일어나는 스왑이 많이 헷갈렸다.
근데 다른 인터넷 설명 찾아보니 되게 간단하게 나왔던...
우선 코드이다.

# 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

l1과 l2를 비교해 작은 쪽이 스왑을 하고 작은 쪽이 l1이 된다는 것의 코드이다.

l1인 124와 l2인 134를 서로 비교하면서 작은쪽이 바뀌게 되는 것이다.

  1. l1(1), l2(1)비교 아무 일도 일어나지 않는다.
    l1. (1)24
    l2. (1)34
  2. l1(2), l2(1)비교 l2가 작으니 스왑.
    l1. 1(2)4 --> 1134
    l2. (1)34 --> 24
  3. l1(3), l2(2) 비교 l2가 작으니 스왑.
    l1. 11(3)4 --> 1124
    l2. (2)4    --> 34
  4. l1(4), l2(3)비교 l2가 작으니 스왑.
    l1. 112(4) --> 11234
    l2. (3)4    --> 4
  5. l1(4), l2(4)비교
    l1. 112344
    l2. none


    return l1 -> 11234가 내가 이해한 답이다...

좋은 웹페이지 즐겨찾기