Giả sử chúng ta được cung cấp một danh sách liên kết có nút bắt đầu là "head", và hai số nguyên m và n. Chúng ta phải duyệt qua danh sách và xóa một số nút chẳng hạn như m nút đầu tiên được giữ trong danh sách và n nút tiếp theo sau khi m nút đầu tiên bị xóa. Chúng tôi thực hiện điều này cho đến khi gặp phần cuối của danh sách liên kết. Chúng tôi bắt đầu từ nút đầu và danh sách liên kết đã sửa đổi sẽ được trả về.
Cấu trúc danh sách liên kết được cung cấp cho chúng tôi là -
Node value : <integer> next : <pointer to next node>
Vì vậy, nếu đầu vào giống như các phần tử =[1, 2, 3, 4, 5, 6, 7, 8], m =3, n =1, thì đầu ra sẽ là [1, 2, 3, 5, 6 , 7,]
Mọi nút sau khi 3 nút bị xóa trong quá trình này, vì vậy cuối cùng danh sách được liên kết sẽ giống như bên dưới -
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
trước:=đầu
-
curr:=đầu
-
q:=0
-
p:=0
-
trong khi curr không phải là null, thực hiện
-
q:=q + 1
-
nếu q giống với m thì
-
đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện
-
nếu curr.next không phải là null thì
-
curr:=next of curr
-
-
-
tiếp theo của trước:=tiếp theo của curr
-
q:=0
-
-
trước:=tiếp theo của trước
-
curr:=next of curr
-
-
quay trở lại đầu
Ví dụ (Python)
Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -
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) Đầu vào
[1, 2, 3, 4, 5, 6, 7, 8], 3, 1
Đầu ra
[1, 2, 3, 5, 6, 7,]