পাইথনে প্রদত্ত লিঙ্কযুক্ত তালিকা থেকে ভাঁজ তালিকা খুঁজে বের করার প্রোগ্রাম

ধরুন আমরা একটি লিঙ্ক তালিকা আছে. আমাদের লিঙ্ক করা তালিকার প্রথম অর্ধেক নিতে হবে এবং দ্বিতীয়ার্ধে ভাঁজ করতে হবে তারপর ছেদকারী নোডগুলিকে তাদের যোগফল নিয়ে একত্রিত করতে হবে। অবশেষে, আমাদের লিঙ্ক করা তালিকার ফলিত হেড ফেরত দিতে হবে।

সুতরাং, যদি ইনপুটটি [5,8,1,2,4,7,5] এর মত হয়, তাহলে আউটপুট হবে [2, 5, 15, 10, ]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• তাপ :=0
• ptr :=নোড
• যদিও ptr নাল না হয়, do
  • temp :=temp + 1
  • ptr :=ptr এর পরবর্তী
• t :=temp / 2 এর ভাগফল
• m :=নোড
• stk :=একটি নতুন স্ট্যাক
• যখন t অ-শূন্য, do
  • m-এর মান stk এ পুশ করুন
  • tmp :=m এর পরের
  • m এর পরের :=null
  • m :=tmp
  • t :=t - 1
• নোড :=m
• যদি temp জোড় হয়, তাহলে
  • m :=m এর পরের
• যদি m শূন্য না হয়, do
  • m এর মান :=m + স্ট্যাক টপ এলিমেন্টের মান।
  • stk থেকে পপ
  • m :=m এর পরের
• রিটার্ন নোড

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

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
def print_list(head):
   ptr = head
   print('[', end = "")
   while ptr:
      print(ptr.val, end = ", ")
      ptr = ptr.next
   print(']')
class Solution:
   def solve(self, node):
      temp = 0
      ptr = node
      while ptr:
         temp += 1
         ptr = ptr.next
      t = temp // 2
      m = node
      stk = []
      while t:
         stk.append(m.val)
         tmp = m.next
         m.next = None
         m = tmp
         t -= 1
      node = m
      if temp % 2 != 0:
         m = m.next
      while m:
         m.val += stk.pop()
         m = m.next
      return node
ob = Solution()
head = make_list([5,8,1,2,4,7,5])
print_list(ob.solve(head))

ইনপুট

[5,8,1,2,4,7,5]

আউটপুট

[2, 5, 15, 10, ]