航海99第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.質問

Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Example 2:

Input: head = [1,2]
Output: [2,1]
Example 3:
Input: head = []
Output: []
Constraints:
The number of nodes in the list is the range [0, 5000].
-5000 <= Node.val <= 5000
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 reverseLL(head: ListNode):
    curr = head
    print('head : ' + str(head.val))
    prev = None

    while curr is not None:
        print('curr : ' + str(curr.val) + ', curr.next : ' + str(curr.next))
        temp = curr.next
        curr.next = prev
        prev = curr
        curr = temp

    return prev


if __name__ == '__main__':

    fifth_node = ListNode(5,None)
    fourth_node = ListNode(4,fifth_node)
    third_node = ListNode(3,fourth_node)
    second_node = ListNode(2,third_node)
    first_node = ListNode(1,second_node)

    result = reverseLL(first_node)

    while (True):
        print('result : ' + str(result.val))
        result = result.next

4.学んだこと

ノードおよびノードのhead、prevおよびvalue

この問題は、単一のチェーンテーブルを使用する問題であり、単一にprevは存在せず、1つの接続のみがあり、ソリューションのprevはheadに代わるリンクである.

5.総評

リンクリスト構造について