Tìm cặp có tích cho trước trong danh sách liên kết đôi đã sắp xếp - Python

Cho danh sách liên kết đôi (doubly linked list) đã sắp xếp chứa các số dương duy nhất. Tìm các cặp trong danh sách có tích bằng giá trị x cho trước. Yêu cầu: không dùng bộ nhớ phụ.

Ví dụ: L = 1 ⇄ 2 ⇄ 4 ⇄ 5 ⇄ 6 ⇄ 8 ⇄ 9, x = 8 → Kết quả: (1, 8), (2, 4)

Thuật toán

1. Khởi tạo con trỏ curr ở đầu (head), nxt ở cuối (tail).
2. Duyệt nxt đến node cuối.
3. Trong khi curr và nxt hợp lệ và khác nhau:
   • Nếu curr.data * nxt.data == x: in cặp, tiến curr lên, lùi nxt xuống.
   • Nếu tích < x: tiến curr lên.
   • Nếu tích > x: lùi nxt xuống.
4. Nếu không tìm thấy cặp nào, in "Not found".

Ví dụ code

class ListNode:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

def insert(head, data):
    node = ListNode(data)
    if head is None:
        return node
    node.next = head
    head.prev = node
    return node

def get_pair_prod(head, x):
    curr = head
    nxt = head
    while nxt.next:
        nxt = nxt.next
    found = False
    while curr and nxt and curr != nxt and nxt.next != curr:
        if curr.data * nxt.data == x:
            found = True
            print(f"({curr.data}, {nxt.data})")
            curr = curr.next
            nxt = nxt.prev
        elif curr.data * nxt.data < x:
            curr = curr.next
        else:
            nxt = nxt.prev
    if not found:
        print("Not found")

# Tạo danh sách: 1 ⇄ 2 ⇄ 4 ⇄ 5 ⇄ 6 ⇄ 8 ⇄ 9
head = None
for val in [9, 8, 6, 5, 4, 2, 1]:
    head = insert(head, val)
x = 8
get_pair_prod(head, x)

Input

head = 1 ⇄ 2 ⇄ 4 ⇄ 5 ⇄ 6 ⇄ 8 ⇄ 9, x = 8

Output

(1, 8)
(2, 4)