Chương trình tìm giao điểm danh sách liên kết từ hai danh sách được liên kết 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 tạo một danh sách liên kết được sắp xếp mới có chứa giao điểm của hai danh sách này.

Vì vậy, nếu đầu vào là L1 =[2, 4, 8] L2 =[3, 4, 8, 10], thì đầu ra sẽ là [4, 8,]

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

• head:=một nút mới có giá trị 0
• cur:=head
• trong khi l1 và l2 không trống, hãy thực hiện
  • nếu giá trị của l1
  • l1:=tiếp theo của l1
• ngược lại khi giá trị của l2
• l2:=tiếp theo của 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):
      head = cur = ListNode(0)
      while l1 and l2:
         if l1.val < l2.val:
            l1 = l1.next
         elif l2.val < l1.val:
            l2 = l2.next
         else:
            cur.next = ListNode(l1.val)
            l1 = l1.next
            l2 = l2.next
            cur = cur.next
      return head.next
ob = Solution()
L1 = make_list([2, 4, 8])
L2 = make_list([3, 4, 8, 10])
print_list(ob.solve(L1, L2))

Đầu vào

[2, 4, 8], [3, 4, 8, 10]

Đầu ra

[4, 8, ]