アルゴリズム 体操24 Middle of the LinkedList

Middle of the LinkedList

単一リンクリストの先頭を指定して、LinkedListの中間ノードを返すメソッドを記述します。
LinkedListのノードの総数が偶数の場合は、2番目の中間ノードを返します。

例

Input: 1 -> 2 -> 3 -> 4 -> 5 -> null
Output: 3

Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
Output: 4

Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null
Output: 4

Solution

力ずく戦略の1つは、最初にLinkedListのノード数を数え、次に2番目の反復で中央のノードを見つけることです。 これを1回の反復で実行できるようにするのが肝です。

fastポインターとslowポインターのメソッドを使用して、fastポインターが常にslowポインターよりもノードの2倍先になるようにします。このように、fastポインターがLinkedListの最後に到達すると、slowポインターは中央のノードを指します。

##実装

class Node:
  def __init__(self, value, next=None):
    self.value = value
    self.next = next


def find_middle_of_linked_list(head):
  # Time Complexity O(N)
  # Space Complexity O(1)
  slow = head
  fast = head
  while (fast is not None and fast.next is not None):
    slow = slow.next
    fast = fast.next.next
  return slow


def main():
  head = Node(1)
  head.next = Node(2)
  head.next.next = Node(3)
  head.next.next.next = Node(4)
  head.next.next.next.next = Node(5)

  print("Middle Node: " + str(find_middle_of_linked_list(head).value))

  head.next.next.next.next.next = Node(6)
  print("Middle Node: " + str(find_middle_of_linked_list(head).value))

  head.next.next.next.next.next.next = Node(7)
  print("Middle Node: " + str(find_middle_of_linked_list(head).value))


main()