アルゴリズムを見つけたいchecks a linked-list with n elements for consistency。リンクリストはdummy head（センチネルノードとも呼ばれます）を使用します。アルゴリズムは、リストを反復処理するために必要なスペースrun in O(n) timeとはuse O(1) extra space別にする必要があり、許可されています。sizeリストのis unknown。さらにそれはforbidden to modify the listです。
前のリストアイテムを指すリストアイテムがある場合、リストは不整合としてカウントされます。最初に最初の要素を格納することを考え、次に現在の要素を最初の要素と比較しながらリストを繰り返し処理します。
これが2番目の質問に対する私の解決策です。
IsConsistent(LinkedList<Item> list) :N
slow = List.Sentinel.next :Element
fast = slow.next :Element
isConsistent = true :boolean
while(fast != list.Sentinel && fast.next != list.Sentinel && isConsistent) do
if(slow == fast)
isConsistent = false
else
slow:= slow.next
fast:= fast.next.next
od
if(isConsistent)
return 0
else
position = 0 : N
slow:= list.Sentinel
while(slow != fast) do
slow:= slow.next
fast:= fast.next
position:= position + 1
od
return position
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加