항해99 2주차 - 두 정렬 리스트의 병합

Today I learned
2022/01/17

회고록

1/17

항해 99, 알고리즘 1주차

교재 : 파이썬 알고리즘 인터뷰

8장 연결 리스트

1. 이론

링크드 리스트란?

연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

노드 구현

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

링크드 리스트 구현

class LinkedList:
    def __init__(self, data):
        self.head = Node(data)
    
    #헤더부터 탐색해 뒤에 새로운 노드 추가하기
    def append(self, data):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(data)
	
    #모든 노드 값 출력
    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

노드 인덱스 알아내기

    def get_node(self, index):
        cnt = 0
        node = self.head
        while cnt < index:
            cnt += 1
            node = node.next
        return node

삽입

    def add_node(self, index, value):
        new_node = Node(value)
        if index == 0:
            new_node.next = self.head
            self.head = new_node
            return
        node = self.get_node(index-1)
        next_node = node.next
        node.next = new_node
        new_node.next = next_node

[5] -> [12] -> [8]를 [5] -> [6] -> [12] -> [8] 만들기 위해서 인덱스 1자리인 12에 들어가기 위해 5 노드 위치를 파악하고, 그 다음 next에 6 노드를 연결한다. [6]의 next는 12가 연결되게끔 해야한다.

삭제

    def delete_node(self, index):
        if index == 0:
            self.head = self.head.next
            return
        node = self.get_node(index-1)
        node.next = node.next.next

삭제하는 것은 더 간단한다. [5] -> [6] -> [12] -> [8]에서 삭제하고자 하는 index 번 째 노드의 전 노드를 찾아 바로 다음 노드가 될 것을 연결해주면 된다.

[5] -> [12] -> [8]
----[6]----

위처럼 1번째 노드인 [6]을 삭제하고자 한다면, 그 전 노드인 [5]의 next를 바로 [12]와 연결해주면 된다.

2. 문제

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.

Example 1:

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

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

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.

https://leetcode.com/problems/reverse-linked-list/

3. MySol

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


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

    list = []

    curr = list1
    curr2 = list2

    while True:

        if curr is None:
            list.append(curr2.val)
            curr2=curr2.next
        elif curr2 is None:
            list.append(curr.val)
            curr=curr.next
        elif curr.val == curr2.val :
            list.append(curr.val)
            list.append(curr2.val)
            curr=curr.next
            curr2=curr2.next
        elif curr.val < curr2.val :
            list.append(curr.val)
            curr=curr.next
        else :
            list.append(curr2.val)
            curr2=curr2.next

        if curr is None and curr2 is None:
            break

    return list


if __name__ == '__main__':

    arr2_third_node = ListNode(4, None)
    arr2_second_node = ListNode(3, arr2_third_node)
    arr2_first_node = ListNode(1, arr2_second_node)

    arr1_third_node = ListNode(3,None)
    arr1_second_node = ListNode(2,arr1_third_node)
    arr1_first_node = ListNode(1,arr1_second_node)

    result = merge_with_sort(arr1_first_node, arr2_first_node)

    print('result : ' + str(result))

4. 배운 점

• 책에는 재귀를 이용한 풀이가 나와 있으나, 아직은 재귀훈련이 익숙치 않아 각 조건문별로 로직을 구현하여 반복문을 돌렸다.

5. 총평

리스트, 반복문 훈련