Hyuntae H

Hyuntae H

배워가는 학생
21.03.29~22.09.28 군대

Python Algorithm Q14

Q14 Merge Two Sorted Lists

Q

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Sample Input

image

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Input: list1 = [], list2 = []
Output: []

Input: list1 = [], list2 = [0]
Output: [0]

Constraints

  • The number of nodes in both lists is in the range [0, 50].
  • -100 <= Node.val <= 100
  • Both list1 and list2 are sorted in non-decreasing order.

1. My Own Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

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

class Solution:
    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
        l1, l2 = list1, list2
        head = None

        #filter of empty cases
        if not l1 and not l2: #both empty case
            return head
        if not l1: #when l1 is empty
            return l2
        if not l2:
            return l1

        #start, init. Declare which to start
        if (l1.val >= l2.val):
            head = l2
            head_node = head #saving head
            l2 = l2.next
            if(not l2): #filter of one letter case
                head.next = l1
                return head_node
        else:
            head = l1
            head_node = head
            l1 = l1.next
            if(not l1):
                head.next = l2
                return head_node
        
        while l1 or l2: #until both are the false
            if (l1.val >= l2.val):
                head.next = l2
                head = head.next
                l2 = l2.next
                if(not l2): #exe when l2 is empty
                    head.next = l1
                    return head_node

            else:
                head.next = l1
                head = head.next
                l1 = l1.next
                if(not l1): #exe when l1 is empty
                    head.next = l2
                    return head_node

        return head_node

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#to test, you have to make to linked-list manually. 
inp1 = [-9,3] # inp1 = [1]
inp2 = [4,5] # inp2 = [3]

#list1_3 = ListNode(inp1[2], None)
list1_2 = ListNode(inp1[1], None)
list1 = ListNode(inp1[0], list1_2)

#list2_3 = ListNode(inp2[2], None)
list2_2 = ListNode(inp2[1], None)
list2 = ListNode(inp2[0], list2_2)

#for test
a = Solution()
a.mergeTwoLists(list1, list2)

Proudly, I do it by myself, with only my own skills. Thus, the solution is pretty messy. I added some additional codes when facing errors. The answer itself is really simple(but quiet confusing). Let’s start from the top.

  1. First one is the filter of empty cases. When both are empty, return none. When one of the two is empty, return the other one as it is.

  2. Second one is declaring which to start. Compare which is the smaller one, then put smaller node to the head and push that node. Never forget to save the head to the head_node. if statement is for filtering one letter case. After pushing the list, when it is none, return the other list.

  3. Third one is starting while loop until both lists are none. Keep comparing the value. Put the smaller node to the head.next(just changing the address, never assign the node itself), and push head & the list. Also check if pushed list met the end. If end, return the other list.

**보충 설명 : 2번, 3번에서 if(not list) 이후 어떤 식으로 return을 했는지 살펴보자. l1이 none으로 변하게 되면, 더 이상 l1에서는 가져올 값이 없다. 계속 l2에서만 가져오면 된다. 그렇다고 while loop를 통해 굳이 계속 반복해서 head.next에 l2를 할당할 이유가 없다. head.next에 l2를 한 번만 넣으면 그 이후로는 head는 l2 node를 계속 따라가게 된다. 그렇기 때문에 한 번만 대입하고 바로 헤드 노드를 리턴 때려버리는 것이다. 어짜피 앞부분에 우리가 손수 넣었던 list들과 나머지 l2 list는 이어졌으니까.

2. Given Solution #1

1
2
3
4
5
6

def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
    if(not l1) or (l2 and l1.val > l2.val): # (l1 is none) or l2 exists and l1 > l2
        l1, l2 = l2, l1
    if l1: #after swaping and l1 exist, change next address to the return of itself.
        l1.next = self.mergeTwoLists(l1.next, l2)
    return l1

If you perfectly understand this solution, you’ll be shocked by the crazy and extreme use of recursion. I’m really impressed by this answer. Start following the answer step by step. +There are some restrictions in use of English, so using korean instead.

  1. 먼저 이 코드부터 시작하자.
    if(not l1) or (l2 and l1.val > l2.val): l1, l2 = l2, l1
    l1이 none 이거나, l2 값이 존재하고 l1 > l2 일 때 두 노드를 swap 한다. 이 줄 자체에는 아주 큰 떡밥(?)이 많이 담겨 있지만 지금은 설명하기 어려우므로 코드의 의미 자체만 설명하려 한다.
    #1 recursion에는 끝이 있어야만 한다. 이 recursion의 끝은 두 l1, l2모두 none일 때이다. 따라서 이 if문에서도 둘 다 none이면 실행되지 않도록 설계하였다.
    #2 l1.val > l2.val 인 경우에만 swap을 진행한다. l1.val <= l2.val인 경우는 따로 생각하지 않는다. 이 답안의 전체적인 콘셉트는, “L1“을 작은 값부터 천천히 비교하며 올라가는 것이다. 그래서 최종 리턴 값이 L1이다. l1이 l2보다 크다면 l2와 swap해서 작은 값부터 쌓아 올린다.

  2. 다음 줄이다.
    if l1: l1.next = self.mergeTwoLists(l1.next, l2)
    recursion을 시작하는 코드이다. l1이 none이 아닐 때까지 실행된다. l1이 가르키는 다음 주소를 재귀함수의 리턴값으로 넣어준다. l1, l2가 모두 none이 되는 순간 l1(=none)을 리턴하면서 모든 리턴이 시작된다.

둘 다 none이 되어 리턴이 시작되면, 먼저 l1.next는 none(첫 리턴 값)을 가르킨다. 즉 현재까지 l1은 none을 가르키는 마지막 노드가 된다. 다시 l1을 return하므로 이번에는 l1.next에 l1이 할당된다. 즉 현재 l1은 마지막에서 두번째 노드가 된다. 이를 계속 반복하면 모든 재귀함수가 return을 완료하고 l1이라는 연결리스트의 head node가 리턴된다.

Overall Review

Recursion itself is confusing + Linked list is complicating = Super Crazy hard to understand. If I didn’t perfectly understand the question #13, maybe I give up this question. But I’m realizing my growth in algorithm skills because I wholly understand this answer in just an hour. As expected, struggling with some crazy problems makes me explosively stronger. Keep challenging!!

참고