「世界で闘うプログラミング力を鍛える本」Pythonコード解答例 - 2.7 交わるノード
###CHAP2. 連結リスト
#Pythonコード解答例
from chap2_function import*
def dll_from_node(node):
dll = DoublyLinkedList()
while(node is not None):
dll.append(node.data)
last = node
node = node.next
return dll
class Result:
# コンストラクタ
def __init__(self, tail, size):
self.tail = tail
self.size = size
def findIntersection(list1,list2):
if list1 == None or list2 == None:
return None
result1 = getTailAndSize(list1)
result2 = getTailAndSize(list2)
if result1.tail != result2.tail:
return None
shorter = list1 if result1.size < result2.size else list2
longer = list2 if result1.size < result2.size else list1
longer = getKthNode(longer,abs(result1.size-result2.size))
while shorter.data != longer.data:
shorter = shorter.next
longer = longer.next
return longer
def getTailAndSize(list_node):
if list_node == None:
return None
size = 1
current = list_node
while current.next:
size = size + 1
current = current.next
return Result(current,size)
def getKthNode(head_node,k):
current = head_node
while k>0 and current:
current = current.next
k = k - 1
return current
dll_1 = DoublyLinkedList()
# DLL: None -> 3(ヘッド) -> 1 -> 5 -> 9 -> 7 -> 2 ->1(ラスト) -> None
dll_1.append(3)
dll_1.append(1)
dll_1.append(5)
dll_1.append(9)
dll_1.append(7)
dll_1.append(2)
dll_1.append(1)
dll_1.printList(dll_1.head)
dll_2 = DoublyLinkedList()
# DLL: None -> 4(ヘッド) -> 6 -> 7 -> 2 ->1(ラスト) -> None
dll_2.append(4)
dll_2.append(6)
dll_2.insertNode(dll_2.head.next,dll_1.head.next.next.next.next)
dll_2.printList(dll_2.head)
result_dll = dll_from_node(findIntersection(dll_1.head,dll_2.head))
result_dll.printList(result_dll.head)
#Python関数(ノードクラス, 双方向リストクラス)
chap2_function.py
# ノードクラス
class Node:
# コンストラクタ
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
# 双方向リストクラス
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)
#参考文献
[1] GeeksforGeeks: Doubly Linked List | Set 1 (Introduction and Insertion)
[2] GeeksforGeeks: Delete a node in a Doubly Linked List