在 Python 中，在已排序的双向链表中查找具有给定乘积的对

pythonserver side programmingprogramming更新于 2025/10/10 23:08:17

假设我们有一个由唯一正数组成的已排序双向链表；我们必须在双向链表中查找乘积与给定值 x 相同的对。我们必须记住，这将在不消耗任何额外空间的情况下得到解决。

因此，如果输入如下 L = 1 ⇔ 2 ⇔ 4 ⇔ 5 ⇔ 6 ⇔ 8 ⇔ 9 且 x = 8，则输出将为 (1, 8), (2, 4)

要解决这个问题，我们将遵循以下步骤 −

curr := head, nxt := head
当 nxt.next 不为 None 且非零时，执行
- nxt := nxt.next
found := False
当 curr 和 nxt 不为空且 curr 和 nxt 不同且 nxt.next 不是 curr 时，执行
- 如果 (curr.data * nxt.data) 与 x 相同，然后
  - found := True
  - 显示一对 curr.data, nxt.data
  - curr := curr.next
  - nxt := nxt.prev
- 否则，
  - if (curr.data * nxt.data) < x，则
    - curr := curr.next
  - 否则，
    - nxt := nxt.prev
如果 found 为 False，则
- 显示 "Not found"

示例

让我们看看下面的实现以便更好地理解 −

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)

输入

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