ধরা যাক দুটি নন-এম্পটি লিঙ্কড লিস্ট দেওয়া আছে। এই দুটি লিস্ট দুটি নন-নেগেটিভ ইন্টিজার রিপ্রেজেন্ট করে। ডিজিটগুলো রিভার্স অর্ডারে সংরক্ষিত। প্রতিটি নোডে শুধু একটি ডিজিট থাকে। দুটি সংখ্যা যোগ করে ফলাফল লিঙ্কড লিস্ট হিসেবে রিটার্ন করতে হবে। دو সংখ্যা に লিডিং জিরো নেই (০ ছাড়া)। যেমন ১২০ + ২৩০ হলে লিঙ্কড লিস্ট হবে [0 → 2 → 1] + [0 → 3 → 2] = [0 → 5 → 3] = ৩৫০।
সমাধানের ধাপসমূহ:
- দুটি লিস্ট l1 এবং l2 নিন। head এবং temp কে null ইনিশিয়ালাইজ করুন
- c := 0
- while l1 and l2 উভয়ই নন-এম্পটি
- l1 নন-এম্পटी হলে a := 0, অন্যথায় a := l1.val
- l2 নন-এম্পটি হলে b := 0, অন্যথায় b := l2.val
- n := a + b + c
- n > 9 হলে c := 1 অন্যথায় 0
- value n mod 10 দিয়ে নতুন নোড তৈরি
- head null হলে head := node এবং temp := node
- অন্যথায় head.next := node, এবং head := node
- l1 := l1-এর নেক্সট নোড (যদি থাকে)
- l2 := l2-এর নেক্সট নোড (যদি থাকে)
- c নন-জিরো হলে নোড := value 1 দিয়ে নতুন নোড, head.next := node
- temp রিটার্ন করুন
উদাহরণ (পাইথন)
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 addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
head = None
temp = None
c = 0
while l1 or l2:
if not l1:
a = 0
else:
a = l1.val
if not l2:
b = 0
else:
b = l2.val
n = a + b + c
c = 1 if n > 9 else 0
node = ListNode(n % 10)
if not head:
head = node
temp = node
else:
head.next = node
head = node
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
if c:
node = ListNode(1)
head.next = node
return temp
ob1 = Solution()
l1 = make_list([0,2,1])
l2 = make_list([0,3,2])
print_list(ob1.addTwoNumbers(l1, l2))
ইনপুট
[0,2,1] [0,3,2]
আউটপুট
[0,5,3]
