โจทย์: กำหนด Doubly Linked List ที่เรียงจากน้อยไปมาก ไม่มีค่าซ้ำ หาคู่ (a, b) ที่ a × b = x โดยไม่ใช้พื้นที่เพิ่มเติม (O(1) space)
วิธีแก้: ใช้ Two Pointers — ตัวหนึ่งเริ่มหัว (curr) อีกตัวเริ่มท้าย (nxt) เลื่อนเข้าหากันตามเงื่อนไขผลคูณ
อัลกอริทึม
- หาโหนดท้าย (nxt) โดยเดินไปจน .next เป็น None
- วนลูปจน curr และ nxt ตรงกันหรือทับซ้อน
- ถ้า curr.data × nxt.data == x → พบคู่ พิมพ์ แล้วเลื่อน curr ไปข้างหน้า nxt ไปข้างหลัง
- ถ้าผลคูณ < x → เลื่อน curr ไปข้างหน้า (ค่าเพิ่มขึ้น)
- ถ้าผลคูณ > x → เลื่อน nxt ไปข้างหลัง (ค่าลดลง)
ตัวอย่างโค้ด
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:
prod = curr.data * nxt.data
if prod == x:
found = True
print(f"({curr.data}, {nxt.data})")
curr = curr.next
nxt = nxt.prev
elif prod < x:
curr = curr.next
else:
nxt = nxt.prev
if not found:
print("Not found")
# สร้างลิสต์: 1 ↔ 2 ↔ 4 ↔ 5 ↔ 6 ↔ 8 ↔ 9
head = None
for val in [9, 8, 6, 5, 4, 2, 1]:
head = insert(head, val)
get_pair_prod(head, 8)
ผลลัพธ์
(1, 8) (2, 4)
สรุป: Two Pointers บน Doubly Linked List เรียงลำดับ ให้ O(n) time และ O(1) space เหมาะสำหรับโจทย์หาคู่ที่มีผลคูณ/ผลรวมคงที่
