Cho danh sách liên kết bắt đầu từ head, và hai số nguyên m, n. Giữ m nút đầu, xóa n nút tiếp theo, lặp lại đến hết danh sách.
Ví dụ: [1,2,3,4,5,6,7,8], m=3, n=1 → [1,2,3,5,6,7].
Thuật toán
- prev = curr = head, q = 0.
- Trong khi curr không null:
- q += 1
- Nếu q == m:
- Lặp n lần: nếu curr.next không null, curr = curr.next.
- prev.next = curr.next
- q = 0
- prev = prev.next
- curr = curr.next
- Trả về head.
Ví dụ (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
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,]