Help us understand the problem. What is going on with this article?

アルゴリズム 体操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()

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away