ภาพรวม
โจทย์: กำหนด 2 sorted linked lists ที่มีโหนดบางตัวซ้ำกัน (common nodes) สร้าง linked list ใหม่ที่มีผลรวมค่าโหนดมากที่สุดจาก head ถึง tail สลับ list ได้เฉพาะที่โหนดซ้ำ (intersection)
ตัวอย่าง
List A: 6 → 8 → 35 → 95 → 115 → 125
List B: 5 → 8 → 17 → 37 → 95 → 105 → 125 → 135
Common nodes: 8, 95, 125
เส้นทางที่ดีที่สุด: 6→8 (A) → 17→37 (B) → 95 (common) → 115→125 (A) → 135 (B)
ผลลัพธ์: [6, 8, 17, 37, 95, 115, 125, 135]
อัลกอริทึม
- ใช้ 2 pointers (current1, current2) เดินพร้อมกัน
- สะสมผลรวม res1, res2 ระหว่าง common nodes
- ที่ common node: เลือก path ที่ผลรวมมากกว่า เชื่อม pointer ตรงข้าม
- ทำซ้ำจนจบทั้ง 2 lists
- ใช้พื้นที่ O(1) เพิ่มเติม
โค้ด Python
class LinkedList:
class ListNode:
def __init__(self, d):
self.data = d
self.next = None
def __init__(self, data_set=[]):
self.head = None
for item in data_set:
self.insert_node(item)
def insert_node(self, new_data):
new_node = self.ListNode(new_data)
new_node.next = self.head
self.head = new_node
def find_max_sum_list(self, a, b):
result = None
prev1, curr1 = a, a
prev2, curr2 = b, b
while curr1 or curr2:
sum1 = sum2 = 0
while curr1 and curr2 and curr1.data != curr2.data:
if curr1.data < curr2.data:
sum1 += curr1.data
curr1 = curr1.next
else:
sum2 += curr2.data
curr2 = curr2.next
if not curr1:
while curr2:
sum2 += curr2.data
curr2 = curr2.next
if not curr2:
while curr1:
sum1 += curr1.data
curr1 = curr1.next
if prev1 == a and prev2 == b:
result = prev1 if sum1 > sum2 else prev2
else:
if sum1 > sum2:
prev2.next = prev1.next
else:
prev1.next = prev2.next
prev1, prev2 = curr1, curr2
if curr1: curr1 = curr1.next
if curr2: curr2 = curr2.next
while result:
print(result.data, end=' ')
result = result.next
my_list1 = LinkedList([125,115,95,35,8,6])
my_list2 = LinkedList([135,125,105,95,37,17,8,5])
my_list1.find_max_sum_list(my_list1.head, my_list2.head)
ผลลัพธ์
6 8 17 37 95 115 125 135
