同じ値の重複は削除する必要があります。head からトラバースされた (リンクされた) リストに、呼び出し後にシーケンス 3,2,8,8,8,5,2,3 が含まれている場合
last = Node(3)
head = Node(2, last)
head = Node(5, head)
head = Node(8, head)
head = Node(8, head)
head = Node(8, head)
head = Node(2, head)
head = Node(3, head)
last.next = head
ここで、head からトラバースされたリストには、3、2、8、5、2 または 2、8、5、2、3 が含まれている必要があります。'head' の値は None に等しく、空のリスト (要素がゼロのリスト) を表します。 . どうすればこれを達成できますか。これは、達成する最も簡単な方法の 1 つかもしれません。私はPythonが初めてなので、これを行うのに苦労しています。
Nodeこれは循環リンク リストであるため、各ノードの値と開始オブジェクト自体を追跡する必要があります。クラスのコードはNode異なる場合がありますが、関数を簡単に変更できるはずです。
class Node(object):
def __init__(self, data, next_=None):
self.data = data
self.next = next_
def ll_remove_dups(curr):
start_node = curr
values_seen = {curr.data}
while curr.next is not start_node:
if curr.next.data in values_seen:
curr.next = curr.next.next
else:
values_seen.add(curr.next.data)
curr = curr.next
def ll_traverse(curr):
start_node = curr
yield curr.data
while curr.next is not start_node:
yield curr.next.data
curr = curr.next
if __name__ == "__main__":
last = Node(3)
head = Node(3, Node(2, Node(8, Node(8, Node(8, Node(5, Node(2, last)))))))
last.next = head
print list(ll_traverse(head)) # [3, 2, 8, 8, 8, 5, 2, 3]
ll_remove_dups(head)
print list(ll_traverse(head)) # [3, 2, 8, 5]
循環リストを反復処理し、既に表示されている値を破棄します (ただし、そのノードが既に表示されているかどうかを最初に確認します)。
基本的には頭から始めて、ノードの値がセットに含まれているかどうかを毎回チェックします。そうでない場合は、値をセットに追加して次に進みます。それ以外の場合は、ノードを削除します (前のノードと次のノードを結合します)。最初のノードに戻ったら (最初のノードを削除することはありません)、停止します。