Pythonで単一リンクリストの中間ノードを見つけるプログラム

単一リンクリストノードがあるとすると、中間ノードの値を見つける必要があります。そして、2つの中間ノードがある場合、2番目のノードを返します。これをシングルパスで解決する必要があります。

したがって、入力が[5,9,6,4,8,2,1,4,5,2]の場合、出力は2になります。

これを解決するために、次の手順に従います-

• p：=ノード

• d：=0、l：=0

• ノードがnullでない場合は、実行してください

  • dが2と同じでない場合、

    • node：=ノードの次

    • l：=l + 1、d：=d + 1

  • それ以外の場合

• p：=pの次、d：=0

  • lが奇数の場合はpの値を返し、それ以外の場合はpの次の値を返します

理解を深めるために、次の実装を見てみましょう

例

class ListNode:
   def __init__(self, data, next = None):
      self.val = data
      self.next = next
   def make_list(elements):
      head = ListNode(elements[0])
   for element in elements[1:]:
      ptr = head
      while ptr.next:
         ptr = ptr.next
         ptr.next = ListNode(element)
      return head
class Solution:
   def solve(self, node):
      p=node
      d=0
      l=0
   while node:
      if d!=2:
         node=node.next
         l+=1
         d+=1
      else:
         p=p.next
         d=0
   return p.val if l & 1 else p.next.val
ob = Solution()
head = make_list([5,9,6,4,8,2,1,4,5,2])
print(ob.solve(head))

入力

Input:
[5,9,6,4,8,2,1,4,5,2]

出力

2