Merge two sorted lists

출처

https://leetcode.com/problems/merge-two-sorted-lists/submissions/

문제

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

예시

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

답1

# 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:
        // 임시 노드를 만든다. 앞으로 여기에 노드들이 쌓일것이다
        temp = ListNode(None)
        // temp노드에 계속 다른 노드들이 연결되어 붙여지기는 하는데, 첫번째 노드의 위치를 모르면 마지막에 정답을 쓸 수 없기 때문에
        // 이렇게, 첫번째 노드의 값을 answer에 저장해 놓는다.
        answer = temp
        
        // 빈 노드가 들어올 때도 있다
        if (l1 is None and l2 is None) :
            return None
        
        // 배열이 아니라 List를 루프 돌려야 하기 때문에 while문을 써준다
        while (True) :

            // l1는 None이 아닌데 l2가 None이라는거는 l2꺼는 다 소진했고, l1에 있는 모든 노드들의 값이 더 크다는 거니까
            if (l1 is not None and l2 is None) :
                // 바로 그냥 전부를 붙여버린다
                temp.next = l1
                break

            // 이것도 위와 마찬가지
            if (l2 is not None and l1 is None) :
                temp.next = l2
                break
            
            // l1와 l2의 노드의 값을 비교해서 작거나 같은놈을 우선적으로
            if (l1.val <= l2.val) :
                // temp노드에 이어 붙인다
                temp.next = ListNode(l1.val)
                // 여기가 재미있는 부분인데, List를 루프돌리기 위해서는 이런식으로 해줘야한다. 배열처럼 index값이 있는게 아니니까 ㅠ
                l1 = l1.next
            else:
                // 마찬가지
                temp.next = ListNode(l2.val)
                l2 = l2.next
            
            // temp노드 다음에 뭔가 붙여야 하니까, 연결될 준비를 하는거지.
            temp = temp.next
        
        // answer는 None Node니까 answer.next값을 돌려주는게 맞다
        return answer.next

답2

# 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:
        // li가 없으면
        if not l1:
            // l2를 고냥 이어 붙인다
            return l2
        // 마찬가지
        if not l2:
            return l1
        // 값을 비교해서
        if l1.val < l2.val:
            // l1의 next에 넣는데,,, 여기서 중요한건 재귀를 사용했다는거야.
            // 그니까 처음에 하나의 노드에서 시작해서, 그 노드를 뺀 다른 노드(l1.next, l2)를 가지고 또 비교를 하는거야.
            // l1.next 하고 l2를 비교해서 더 작은놈을 l1.next에 때려넣고, l1를 돌려주면, 계속 뒤에 이어 붙겠지. 그니까 이거는 재귀적으로 next를 찾는 과정인거야. 더 작은놈을
            // 계속 next에 넣는거지. 그 넣어진거 빼고 나머지들끼리 또 비교해서, 또 넣고 그거를 리턴하고 넣고 리턴하고 하다보면,,, 순서대로 정렬되서 맨 처음의 l1(혹은 l2)에 쫘라라락 붙는거겠지.
            l1.next = self.mergeTwoLists(l1.next, l2) 
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

댓글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다

Up Next:

Valid Parentheses

Valid Parentheses