링크드 리스트(정렬된 리스트 합치기)

정렬된 두 개의 링크드 리스트를 합치는(정렬하여) 문제이다.

 

 

# Title : 두개의 정렬된 linked Lists 합치기
# Chapter : Linked List
# 문제 : 주어진 두개의 정렬된 LinkedList를 정렬이 된 상태로 합쳐라
# L1 : 1→3→5→7
# L2 : 1→2→3→4
# L1+L2 : 1→1→2→3→3→4→5→7

from typing import List

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

def createList(in_list:List[int])-> ListNode:
    if len(in_list) == 0:
        raise RuntimeError('in_list must have data')
    head_node = ListNode(in_list[0])
    last_node = head_node
    for idx in range(1, len(in_list)):
        node = ListNode(in_list[idx])
        last_node.next = node
        last_node = node
    return head_node

def printNodes(node:ListNode) -> None:
    crnt_node = node
    while crnt_node is not None:
        print(crnt_node.val, end=' ')
        crnt_node = crnt_node.next
    print()

class MergeTwoLists:
    def iterativeWay(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy_node = ListNode(0)
        crnt_node = dummy_node

        node1 = l1
        node2 = l2

        while node1 and node2:
            if node1.val <= node2.val:
                crnt_node.next = node1
                node1 = node1.next
                crnt_node = crnt_node.next
            else:
                crnt_node.next = node2
                node2 = node2.next
                crnt_node = crnt_node.next
        if node1:
            crnt_node.next = node1
        else:
            crnt_node.next = node2

        return dummy_node.next

    def recursiveWay(self, l1: ListNode, l2:ListNode) -> ListNode:
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        
        if l1.val <= l2.val:
            l1.next = self.recursiveWay(l1.next, l2)
            return l1
        else:
            l2.next = self.recursiveWay(l1, l2.next)
            return l2

#itearative Way
list1 = createList([1,3,5,7])
list2 = createList([1,2,3,4])

merger = MergeTwoLists()
merged_head = merger.iterativeWay(list1,list2)
printNodes(merged_head)
        
#recursive Way
list1 = createList([1,3,5,7])
list2 = createList([1,2,3,4])

merger = MergeTwoLists()
merged_head = merger.recursiveWay(list1,list2)
printNodes(merged_head)

 

참조 : (1) 코딩 테스트, 초급, 정렬된 리스트 합치기 - YouTube