สมมติว่าเราได้รับรายการเชื่อมโยงที่มีโหนดเริ่มต้นเป็น "หัว" และเลขจำนวนเต็มสองตัว m และ n เราต้องสำรวจรายการและลบโหนดบางโหนดเช่นโหนด m แรกจะถูกเก็บไว้ในรายการและโหนดถัดไป n โหนดหลังจาก m โหนดแรกถูกลบ เราดำเนินการนี้จนกว่าเราจะพบจุดสิ้นสุดของรายการที่เชื่อมโยง เราเริ่มจากเฮดโหนด และรายการลิงก์ที่แก้ไขจะถูกส่งคืน
โครงสร้างรายการที่เชื่อมโยงจะได้รับเป็น -
Node value : <integer> next : <pointer to next node>
ดังนั้น หากอินพุตเป็นเหมือนองค์ประกอบ =[1, 2, 3, 4, 5, 6, 7, 8], m =3, n =1, ผลลัพธ์จะเป็น [1, 2, 3, 5, 6 , 7, ]
ทุกโหนดหลังจาก 3 โหนดจะถูกลบในกระบวนการนี้ ดังนั้นในท้ายที่สุดรายการที่เชื่อมโยงจะมีลักษณะดังนี้ -
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ก่อนหน้า :=หัว
-
curr :=หัว
-
q :=0
-
p :=0
-
ในขณะที่สกุลเงินไม่เป็นโมฆะให้ทำ
-
q :=q + 1
-
ถ้า q เท่ากับ m แล้ว
-
สำหรับผมอยู่ในช่วง 0 ถึง n ทำ
-
ถ้า curr.next ไม่เป็นโมฆะ
-
curr :=ถัดไปของ curr
-
-
-
ถัดไปของก่อนหน้า :=ถัดไปของสกุลเงิน
-
q :=0
-
-
ก่อนหน้า :=ถัดไปของก่อนหน้า
-
curr :=ถัดไปของ curr
-
-
กลับหัว
ตัวอย่าง (Python)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
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(head, m, n):
prev = curr = head
q = 0
p = 0
while curr:
q += 1
if q == m:
for i in range(n):
if curr.next is not None:
curr = curr.next
prev.next = curr.next
q = 0
prev = prev.next
curr = curr.next
return head
head = ListNode()
elements = [1, 2, 3, 4, 5, 6, 7, 8]
head = make_list(elements)
res = solve(head, 3, 1)
print_list(res) อินพุต
[1, 2, 3, 4, 5, 6, 7, 8], 3, 1
ผลลัพธ์
[1, 2, 3, 5, 6, 7,]
