Tìm các cặp với sản phẩm đã cho trong Danh sách được liên kết đôi được sắp xếp bằng Python

Giả sử chúng ta có một danh sách liên kết kép được sắp xếp gồm các số dương duy nhất; chúng ta phải tìm các cặp trong danh sách được liên kết kép có sản phẩm giống với một giá trị x cho trước. Chúng tôi phải ghi nhớ rằng, điều này sẽ được giải quyết mà không tốn thêm dung lượng.

Vì vậy, nếu đầu vào là L =1 ⇔ 2 ⇔ 4 ⇔ 5 ⇔ 6 ⇔ 8 ⇔ 9 và x =8, thì đầu ra sẽ là (1, 8), (2, 4)

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

• curr:=head, nxt:=head

• trong khi nxt.next không phải Không có là khác 0, hãy làm

  • nxt:=nxt.next

• tìm thấy:=Sai

• trong khi curr và nxt không phải là null và curr và nxt là khác nhau và nxt.next không phải là curr, thực hiện

  • nếu (curr.data * nxt.data) giống với x, thì

    • tìm thấy:=True

    • hiển thị một cặp curr.data, nxt.data

    • curr:=curr.next

    • nxt:=nxt.prev

  • nếu không,

    • if (curr.data * nxt.data)

      • curr:=curr.next

    • nếu không,

      • nxt:=nxt.prev

• nếu tìm thấy là Sai, thì

  • hiển thị "Không tìm thấy"

Ví dụ

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

class ListNode:
   def __init__(self, data):
      self.data = data
      self.prev = None
      self.next = None
def insert(head, data):
   node = ListNode(0)
   node.data = data
   node.next = node.prev = None
   if (head == None):
      (head) = node
   else :
      node.next = head
      head.prev = node
      head = node
   return head
def get_pair_prod(head, x):
   curr = head
   nxt = head
   while (nxt.next != None):
      nxt = nxt.next
   found = False
   while (curr != None and nxt != None and curr != nxt and nxt.next != curr) :
      if ((curr.data * nxt.data) == x) :
         found = True
         print("(", curr.data, ", ", nxt.data, ")")
         curr = curr.next
         nxt = nxt.prev
      else :
         if ((curr.data * nxt.data) < x):
            curr = curr.next
         else:
            nxt = nxt.prev
   if (found == False):
      print( "Not found")
head = None
head = insert(head, 9)
head = insert(head, 8)
head = insert(head, 6)
head = insert(head, 5)
head = insert(head, 4)
head = insert(head, 2)
head = insert(head, 1)
x = 8
get_pair_prod(head, x)

Đầu vào

head = None
head = insert(head, 9)
head = insert(head, 8)
head = insert(head, 6)
head = insert(head, 5)
head = insert(head, 4)
head = insert(head, 2)
head = insert(head, 1)
x = 8

Đầu ra

( 1 , 8 )
( 2 , 4 )