「世界で闘うプログラミング力を鍛える本」Pythonコード解答例 - 2.8 ループの検出

###CHAP2. 連結リスト

#Pythonコード解答例


from chap2_function import* 

def FindBeginning(head_node):
    
    slow = head_node
    fast = head_node

    while fast and fast.next:

        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            break

    if fast == None or fast.next == None:
        return None

    slow = head_node

    while slow != fast:
        slow = slow.next
        fast = fast.next

    return fast


sll = SinglyLinkedList()

sll.append(1)
sll.append(2)
sll.append(3)
sll.append(4)
sll.append(5)

sll.printList(sll.head)

sll.insertNode(sll.head.next.next.next.next,sll.head.next.next)

print("sll[0]: ", sll.head.data)
print("sll[1]: ",sll.head.next.data)
print("sll[2]: ",sll.head.next.next.data)
print("sll[3]: ",sll.head.next.next.next.data)
print("sll[4]: ",sll.head.next.next.next.next.data)
print("sll[5]: ",sll.head.next.next.next.next.next.data)
print("sll[6]: ",sll.head.next.next.next.next.next.next.data)

print("出力: ",FindBeginning(sll.head).data)

#Python関数(ノードクラス, 双方向リストクラス)

chap2_function.py

# ノードクラス
class Node: 
  
    # コンストラクタ
    def __init__(self, data): 
        self.data = data 
        self.next = None
        self.prev = None
  
# 単方向リストクラス
class SinglyLinkedList: 
  
    # コンストラクタ
    def __init__(self): 
        self.head = None

    def insertNode(self, prev_node, new_node): 
  
        if prev_node is None: 
            print("the given previous node cannot be NULL")
            return 
        
        if new_node is None: 
            print("the given new node cannot be NULL")
            return 
  
        # prev_nodeで指定したノードの次ノードを新ノードにする
        prev_node.next = new_node 
  
  
    # 最終ノードからのノード挿入
    def append(self, new_data): 
  
        # ノード生成 
        new_node = Node(new_data) 
  
        # 新ノードの次ノードをNone定義
        new_node.next = None
  
        # もしヘッドノードが設定されていない（空のリスト）場合、新ノードをヘッドノードに設定する
        if self.head is None: 
            new_node.prev = None
            self.head = new_node 
            return 
  
        # 最終ノードを設定する（順方向走査）
        last = self.head 
        while(last.next is not None): 
            last = last.next
  
        # 新ノードを最終ノードに指定する
        last.next = new_node 
  
        return

    # This function prints contents of linked list 
    # starting from the given node 
    def printList(self, node): 

        last = None
  
        print("単方向リスト: \n") 

        print("順方向走査")
        while(node is not None): 
            print(node.data,end="") 
            last = node 
            node = node.next
            if node:
                print(" -> ",end="")
            else:
                print("\n")
  


# 双方向リストクラス
class DoublyLinkedList: 
  
    # コンストラクタ
    def __init__(self): 
        self.head = None
  
    # 第一ノードからのノード挿入
    def push(self, new_data): 
  
        # ノード生成
        new_node = Node(new_data) 
  
        # 新ノードの次ノードをそもそもヘッドノードだったものにする
        new_node.next = self.head 
  
        # そもそもヘッドノードだったものの前ノードを新ノードにする
        if self.head is not None: 
            self.head.prev = new_node 
  
        # 新ノードをヘッドノードにする
        self.head = new_node 
  
    # 中間地点でのノード挿入 
    def insert(self, prev_node, new_data): 
  
        # prev_nodeで指定したノードの後にノード挿入するか指定
        # もしNoneの場合は、関数を出る
        if prev_node is None: 
            print("the given previous node cannot be NULL")
            return 
  
        # ノード生成
        new_node = Node(new_data) 
  
        # 新ノードの次ノードをprev_nodeで指定したノードの次ノードにする
        new_node.next = prev_node.next
  
        # prev_nodeで指定したノードの次ノードを新ノードにする
        prev_node.next = new_node 
  
        # 新ノードの前ノードをprev_nodeで指定したノードにする
        new_node.prev = prev_node 
  
        # 新ノードの次ノードをprev_nodeで指定したノードの次ノードにしたが、そのノードの前ノードも新ノードにする
        if new_node.next is not None: 
            new_node.next.prev = new_node 

    def insertNode(self, prev_node, new_node): 
  
        # prev_nodeで指定したノードの後にノード挿入するか指定
        # もしNoneの場合は、関数を出る
        if prev_node is None: 
            print("the given previous node cannot be NULL")
            return 
        
        if new_node is None: 
            print("the given new node cannot be NULL")
            return 
  
        # prev_nodeで指定したノードの次ノードを新ノードにする
        prev_node.next = new_node 
  
        # 新ノードの前ノードをprev_nodeで指定したノードにする
        new_node.prev = prev_node 
  
  
    # 最終ノードからのノード挿入
    def append(self, new_data): 
  
        # ノード生成 
        new_node = Node(new_data) 
  
        # 新ノードの次ノードをNone定義
        new_node.next = None
  
        # もしヘッドノードが設定されていない（空のリスト）場合、新ノードをヘッドノードに設定する
        if self.head is None: 
            new_node.prev = None
            self.head = new_node 
            return 
  
        # 最終ノードを設定する（順方向走査）
        last = self.head 
        while(last.next is not None): 
            last = last.next
  
        # 新ノードを最終ノードに指定する
        last.next = new_node 
  
        # 7. 新ノードの前ノードをそもそも最終ノードだったものにする
        new_node.prev = last 
  
        return
  
    def delete(self,del_node):

        if self.head == None or del_node == None: 
            return 

        if self.head == del_node: 
            self.head = del_node.next

        if del_node.next != None: 
            del_node.next.prev = del_node.prev 

        if del_node.prev != None: 
            del_node.prev.next = del_node.next

    # This function prints contents of linked list 
    # starting from the given node 
    def printList(self, node): 

        last = None
  
        print("双方向リスト: \n") 

        print("順方向走査")
        while(node is not None): 
            print(node.data,end="") 
            last = node 
            node = node.next
            if node:
                print(" -> ",end="")
            else:
                print("\n")
  
        print("逆方向走査")
        while(last is not None): 
            print(last.data,end="")
            last = last.prev 
            if last:
                print(" -> ",end="")
            else:
                print("\n")
  
if __name__ == '__main__':
    # 空の双方向リストの生成
    # DLL: None
    dll = DoublyLinkedList() 
    # DLL: None -> 6(ヘッド/ラスト) -> None
    dll.append(6) 
    # DLL: None -> 7(ヘッド) -> 6(ラスト) -> None 
    dll.push(7) 
    # DLL: None -> 1(ヘッド) -> 7 -> 6(ラスト) -> None 
    dll.push(1) 
    # DLL: None -> 1(ヘッド) -> 7 -> 6 -> 4(ラスト) -> None 
    dll.append(4) 
    # DLL: None -> 1(ヘッド) -> 7 -> 8 -> 6 -> 4(ラスト) -> None 
    dll.insert(dll.head.next, 8) 
    # DLL: None -> 1(ヘッド) -> 8 -> 6 -> 4(ラスト) -> None 
    dll.delete(dll.head.next) 


    dll.printList(dll.head) 

    sll = SinglyLinkedList()

    sll.append(1)
    sll.append(8)
    sll.append(6)
    sll.append(4)

    sll.printList(sll.head)

#参考文献
[1] GeeksforGeeks: Doubly Linked List | Set 1 (Introduction and Insertion)
[2] GeeksforGeeks: Delete a node in a Doubly Linked List