992週間の航行-2つのソート・リストをマージ

Today I learned
2022/01/17
回顧録

1/17

航行99、アルゴリズム1週目
教材:Pythonアルゴリズムインタビュー
第8章接続リスト

1.理論

リンクリストとは?
接続リスト、リンクリスト(linklist)は、ノードごとに1行のデータとポインタを持つようにデータを格納するデータ構造である.名前の通り、データを含むノードが接続され、ノード上のポインタが次のノードまたは前のノードとの接続を担当します.
ノード実装

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ノードの位置を決定し、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]では、削除するインデックスの2番目のノードの前のノードを見つけ、次のノードに接続します.
[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.総評

練習を重ねる