สมมติว่าเรามีรายการเชื่อมโยงสองรายการ L1 และ L2 ที่มีความยาว m และ n ตามลำดับ เรายังมีตำแหน่ง a และ b สองตำแหน่ง เราต้องลบโหนดออกจาก L1 จากโหนด a-th ไปยังโหนด b-th node และรวม L2 เข้าด้วยกัน
ดังนั้น ถ้าอินพุตเป็นเหมือน L1 =[1,5,6,7,1,6,3,9,12] L2 =[5,7,1,6] a =3 b =6 ผลลัพธ์ก็จะออกมา เป็น [1, 5, 6, 5, 7, 1, 6, 9, 12]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- head2 :=L2, อุณหภูมิ :=L2
- ในขณะที่ temp มีโหนดถัดไป ให้ทำ
- อุณหภูมิ :=ถัดไปของอุณหภูมิ
- tail2 :=อุณหภูมิ
- นับ :=0
- อุณหภูมิ :=L1
- end1 :=null, start3 :=null
- ในขณะที่ temp ไม่เป็นค่าว่าง ให้ทำ
- ถ้าการนับเท่ากับ a-1 แล้ว
- end1 :=อุณหภูมิ
- ถ้าการนับเท่ากับ b+1 แล้ว
- start3 :=อุณหภูมิ
- ออกมาจากลูป
- อุณหภูมิ :=ถัดไปของอุณหภูมิ
- นับ :=นับ + 1
- ถ้าการนับเท่ากับ a-1 แล้ว
- ถัดไปจาก end1 :=head2
- ถัดจาก tail2 :=start3
- คืน L1
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
class ListNode:
def __init__(self, data, next = None):
self.val = data
self.next = next
def make_list(elements):
head = ListNode(elements[0])
for element in elements[1:]:
ptr = head
while ptr.next:
ptr = ptr.next
ptr.next = ListNode(element)
return head
def print_list(head):
ptr = head
print('[', end = "")
while ptr:
print(ptr.val, end = ", ")
ptr = ptr.next
print(']')
def solve(L1, L2, a, b):
head2 = temp = L2
while temp.next:
temp = temp.next
tail2 = temp
count = 0
temp = L1
end1, start3 = None, None
while temp:
if count == a-1:
end1 = temp
if count == b+1:
start3 = temp
break
temp = temp.next
count += 1
end1.next = head2
tail2.next = start3
return L1
L1 = [1,5,6,7,1,6,3,9,12]
L2 = [5,7,1,6]
a = 3
b = 6
print_list(solve(make_list(L1), make_list(L2), a, b)) อินพุต
[1,5,6,7,1,6,3,9,12], [5,7,1,6], 3, 6
ผลลัพธ์
[1, 5, 6, 5, 7, 1, 6, 9, 12, ]
