Menu
CoddyTech

Reverse Nodes in k-Group

Danh sách liên kết đơn (singly linked list) được lưu trong hai mảng có cùng độ dài. Nút i chứa values[i] và liên kết đến nút next[i]; -1 đánh dấu điểm kết thúc danh sách, còn nút đầu là nút 0. Các nút có thể được lưu theo bất kỳ thứ tự nào, vì vậy hãy lần theo các liên kết, không phải thứ tự trong mảng.

Đảo ngược danh sách theo từng nhóm gồm k nút: k nút đầu tiên sẽ được đảo ngược, tiếp theo là nhóm k nút kế tiếp, cứ thế tiếp tục. Nhóm cuối cùng có ít hơn k nút sẽ giữ nguyên thứ tự. Trả về các giá trị theo thứ tự mới của danh sách.

Hàm

reverseKGroup(next: integer-array, values: integer-array, k: integer) → integer-array
nextinteger-array
chỉ số của nút mà mỗi nút liên kết đến, hoặc -1 nếu là nút cuối cùng
valuesinteger-array
giá trị mà mỗi nút lưu giữ
kinteger
số nút trong mỗi nhóm cần đảo ngược
Trả vềinteger-array
các giá trị theo thứ tự trong danh sách mới

Ràng buộc

  • 1 ≤ L ≤ 5000, trong đó L là độ dài của next và values.
  • -1000 ≤ values[i] ≤ 1000
  • 1 ≤ k ≤ L
  • Mỗi next[i] là -1 hoặc chỉ số nút từ 0 đến L-1.
  • Bắt đầu từ nút 0, danh sách đi qua mỗi nút đúng một lần rồi đến -1. Không có chu trình.

Ví dụ

Đầu vào
next = [2, 3, 4, -1, 1]values = [1, 4, 2, 5, 3]k = 2
Đầu ra
[2, 1, 4, 3, 5]
Giải thích
Danh sách có các giá trị 1, 2, 3, 4, 5 (các nút 0, 2, 4, 1, 3). Các cặp 1, 2 và 3, 4 bị đảo ngược, còn 5 đứng riêng lẻ, ngắn hơn k = 2, nên vẫn ở cuối.
challenge icon

Câu hỏi mở rộng

Bạn có thể viết hàm này bằng đệ quy, đảo ngược một nhóm rồi gọi đệ quy với phần còn lại của danh sách không? Cách này dùng thêm bao nhiêu bộ nhớ?

Đặt lại code
def reverseKGroup(next, values, k):
    # Viết code tại đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

next = [2, 3, 4, -1, 1]
values = [1, 4, 2, 5, 3]
k = 2

Đầu ra mong đợi

[2, 1, 4, 3, 5]