Chương trình tìm sự kết hợp của hai danh sách liên kết đã cho bằng Python

Giả sử chúng ta có hai danh sách liên kết được sắp xếp L1 và L2, chúng ta phải trả về một danh sách liên kết được sắp xếp mới là sự kết hợp của hai danh sách đã cho.

Vì vậy, nếu đầu vào giống như L1 =[10,20,30,40,50,60,70] L2 =[10,30,50,80,90], thì đầu ra sẽ là [10, 20, 30, 40, 50, 60, 70, 80, 90,]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm giải quyết (). Điều này sẽ chiếm L1, L2
• nếu L1 trống, thì
  • trả về L2
• nếu L2 trống, thì
  • trả về L1
• nếu giá trị của L1
• res:=L1
• tiếp theo của res:=giải quyết (tiếp theo của L1, L2)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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, L1, L2):
      if not L1:
         return L2
      if not L2:
         return L1
      if L1.val < L2.val:
         res = L1
         res.next = self.solve(L1.next, L2)
      elif L2.val < L1.val:
         res = L2
         res.next = self.solve(L2.next, L1)
      else:
         res = L1
         res.next = self.solve(L1.next, L2.next)
   return res
ob = Solution()
L1 = make_list([10,20,30,40,50,60,70])
L2 = make_list([10,30,50,80,90])
print_list(ob.solve(L1, L2))

Đầu vào

[10,20,30,40,50,60,70], [10,30,50,80,90]

Đầu ra

[10, 20, 30, 40, 50, 60, 70, 80, 90, ]