[Python] 연결 리스트 <두 정렬 리스트 병합>

사실, 한참 전에 풀이를 시작했는데, 연결리스트의 조회나, 삭제와 같은 기능의 구조를 이해하고 구현해서 문제에 적용시키는데 굉장히 오랜 시간이 걸렸다. 자바의 경우 Util 패키지에서 해당 자료 구조의 객체를 지원하지만, 파이썬은(아마 내 생각엔) 리스트가 어느 정도 연결리스트의 역할을 하기 때문에 굳이 내장 객체를 지원하지 않는 것 같다.

 

바로 풀이를 보자.

 

---

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


class LinkedList:
    def __init__(self):
        head_node = ListNode(None)
        self.head = head_node
        self.tail = head_node
        self.num_of_data = 0

    def insert(self, data):
        insert_node = ListNode(data)
        self.tail.next = insert_node
        self.tail = insert_node
        self.num_of_data += 1

    def delete(self):
        if self.num_of_data == 0:
            print("empty")
            return False
        elif self.num_of_data == 1:
            delete_node = self.head.next
            self.head.next = None
            self.tail = self.head
            self.num_of_data -= 1
            print(delete_node.val, "데이터를 삭제하였습니다.")
            return delete_node.val
        else:
            delete_node = self.head.next
            self.head.next = self.head.next.next
            self.num_of_data -= 1
            print(delete_node.val, "데이터를 삭제하였습니다.")
            return delete_node.val

    def search(self, data):
        check = self.head
        for i in range(self.num_of_data):
            if check.next.val == data:
                print(data, "데이터의 위치: ", i + 1)
                return None
            check = check.next
        print(data, "데이터는 리스트에 없습니다.")
        return None

    def listNum(self):
        print(self.num_of_data)
        return self.num_of_data

    def printList(self):
        current = self.head
        if self.num_of_data == 0:
            print("empty")
            return None
        print(end='')
        for i in range(self.num_of_data - 1):
            print(current.next.val, "->", end='')
            current = current.next
        print(current.next.val)


linked_list = LinkedList()


def margeTwoLists(list1: ListNode, list2: ListNode):

    if (not list1) or (list2 and list1.val > list2.val):
        list1, list2 = list2, list1

    if list1:
        linked_list.insert(list1.val)
        list1.next = margeTwoLists(list1.next, list2)

    return list1


if __name__ == '__main__':
    linked1 = [1, 2, 4]
    linked2 = [1, 3, 4]
    l1 = LinkedList()
    l2 = LinkedList()

    for i in range(len(linked1)):
        l1.insert(linked1[i])
        l2.insert(linked2[i])

    margeTwoLists(l1.head.next, l2.head.next)
    linked_list.printList()

우선 LinkedList 클래스를 따로 생성한 뒤에 필수적인 기능 몇가지를 구현하여, 쉽게 사용할 수 있도록 했다. 이후 margeTwoLists 함수를 재귀로 돌려서 비교 & 스왑하여 전역으로 선언해놓은 linked_list에 삽입하여 조회하면, 풀이는 완료가 된다.

---