पायथन में एकल लिंक की गई सूची के मध्य नोड को खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक एकल लिंक्ड सूची नोड है, हमें मध्य नोड का मान ज्ञात करना है। और जब दो मध्य नोड होंगे, तो हम दूसरे को वापस कर देंगे। हमें इसे सिंगल पास में हल करने का प्रयास करना होगा।

इसलिए, अगर इनपुट [5,9,6,4,8,2,1,4,5,2] जैसा है, तो आउटपुट 2 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे-

• p:=नोड

• डी:=0, एल:=0

• जबकि नोड शून्य नहीं है, करें

  • यदि d 2 के समान नहीं है, तो

    • नोड:=नोड के आगे

    • एल:=एल + 1, डी:=डी + 1

  • अन्यथा,

• p:=p के आगे, d:=0

  • p का ​​रिटर्न वैल जब l विषम हो अन्यथा 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