Đề bài:
Cho head của một danh sách liên kết, đảo ngược các nút của danh sách theo từng nhóm k nút và trả về danh sách đã được thay đổi.
k là một số nguyên dương và nhỏ hơn hoặc bằng độ dài của danh sách liên kết. Nếu số lượng nút không chia hết cho k, thì các nút còn lại ở cuối danh sách sẽ được giữ nguyên.
Bạn không được thay đổi các giá trị trong các nút của danh sách, chỉ có thể thay đổi các nút chính nó.
Ví dụ 1:
Input: head = [1,2,3,4,5], k = 2 Output: [2,1,4,3,5]
Ví dụ 2:
Input: head = [1,2,3,4,5], k = 3 Output: [3,2,1,4,5]
Ràng buộc:
- Số lượng nút trong danh sách là n.
- 1 <= k <= n <= 5000
- 0 <= giá trị của nút <= 1000.
Cách 1: Recursive
Giải thích thuật toán bằng C++
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if (head == nullptr)
return nullptr;
ListNode* tail = head;
for (int i = 0; i < k; ++i) {
// There are less than k nodes in the list, do nothing.
if (tail == nullptr)
return head;
tail = tail->next;
}
ListNode* newHead = reverse(head, tail);
head->next = reverseKGroup(tail, k);
return newHead;
}
private:
// Reverses [head, tail).
ListNode* reverse(ListNode* head, ListNode* tail) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != tail) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
};
Đoạn mã trên triển khai một thuật toán để đảo ngược từng nhóm gồm k nút trong một danh sách liên kết.
Thuật toán này sử dụng đệ quy để đảo ngược danh sách liên kết theo nhóm k nút. Thuật toán được triển khai trong hàm `reverseKGroup`, nhận vào con trỏ `head` trỏ đến đầu danh sách liên kết và một số nguyên `k` đại diện cho số lượng nút trong mỗi nhóm.
Trước khi thực hiện đảo ngược, thuật toán kiểm tra xem danh sách liên kết có đủ nút để tạo thành một nhóm k không. Nếu không đủ, nghĩa là danh sách đã được đảo ngược hoàn toàn hoặc còn lại ít hơn k nút, thuật toán trả về `head` ban đầu và kết thúc đệ quy.
Nếu danh sách liên kết có đủ nút để tạo thành một nhóm k, thuật toán tiến hành đảo ngược nhóm này bằng cách gọi hàm `reverse` với `head` và `tail`. Hàm `reverse` sẽ đảo ngược danh sách từ `head` đến trước `tail` và trả về con trỏ đến nút đầu sau khi đảo ngược.
Sau khi đảo ngược nhóm, con trỏ `next` của `head` được gán bằng kết quả của đệ quy `reverseKGroup` trên `tail` (nhóm tiếp theo). Điều này để liên kết nhóm đã đảo ngược với nhóm tiếp theo sau khi đảo ngược danh sách liên kết.
Cuối cùng, thuật toán trả về con trỏ đến nút đầu của danh sách liên kết đã được đảo ngược.
Hàm `reverse` được triển khai để đảo ngược danh sách liên kết từ `head` đến trước `tail`. Nó sử dụng hai con trỏ `prev` và `curr` để theo dõi nút trước và nút hiện tại trong quá trình đảo ngược. Thuật toán duyệt từ `head` đến `tail` và thực hiện việc cập nhật liên kết giữa các nút để đảo ngược danh sách liên kết. Cuối cùng, hàm trả về con trỏ đến nút đầu sau khi đảo ngược.
Ví dụ, nếu danh sách liên kết ban đầu là 1 -> 2 -> 3 -> 4 -> 5 và k = 2, sau khi áp dụng thuật toán, danh sách liên kết sẽ trở thành 2 -> 1 -> 4 -> 3 -> 5.
Giải thích thuật toán bằng Java
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null)
return null;
ListNode tail = head;
for (int i = 0; i < k; ++i) {
// There are less than k nodes in the list, do nothing.
if (tail == null)
return head;
tail = tail.next;
}
ListNode newHead = reverse(head, tail);
head.next = reverseKGroup(tail, k);
return newHead;
}
// Reverses [head, tail).
private ListNode reverse(ListNode head, ListNode tail) {
ListNode prev = null;
ListNode curr = head;
while (curr != tail) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
Giải thích thuật toán bằng Python
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if not head:
return None
tail = head
for _ in range(k):
# There are less than k nodes in the list, do nothing.
if not tail:
return head
tail = tail.next
newHead = self._reverse(head, tail)
head.next = self.reverseKGroup(tail, k)
return newHead
def _reverse(self, head: Optional[ListNode], tail: Optional[ListNode]) -> Optional[ListNode]:
"""Reverses [head, tail)."""
prev = None
curr = head
while curr != tail:
next = curr.next
curr.next = prev
prev = curr
curr = next
return prev
Cách 2: Iterative
Giải thích thuật toán bằng C ++
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if (!head || k == 1)
return head;
const int length = getLength(head);
ListNode dummy(0, head);
ListNode* prev = &dummy;
ListNode* curr = head;
for (int i = 0; i < length / k; ++i) {
for (int j = 0; j < k - 1; ++j) {
ListNode* next = curr->next;
curr->next = next->next;
next->next = prev->next;
prev->next = next;
}
prev = curr;
curr = curr->next;
}
return dummy.next;
}
private:
int getLength(ListNode* head) {
int length = 0;
for (ListNode* curr = head; curr; curr = curr->next)
++length;
return length;
}
};
Đoạn mã trên triển khai một thuật toán để đảo ngược từng nhóm gồm k nút trong một danh sách liên kết.
Thuật toán này sử dụng một con trỏ `dummy` để làm đầu và một con trỏ `prev` để theo dõi nút trước nhóm hiện tại. Ban đầu, con trỏ `prev` được khởi tạo để trỏ đến nút `dummy`, còn con trỏ `curr` được khởi tạo để trỏ đến nút đầu tiên của danh sách liên kết (`head`).
Thuật toán sử dụng một vòng lặp bên ngoài để xử lý từng nhóm k nút. Số lượng nhóm được xác định bằng cách tính độ dài của danh sách liên kết (`length`) và chia cho k.
Trong vòng lặp bên ngoài, thuật toán sử dụng một vòng lặp bên trong để đảo ngược từng nhóm k nút. Trong vòng lặp bên trong, con trỏ `next` được sử dụng để lưu trữ con trỏ tới nút tiếp theo sau `curr` (tức là nút thứ hai trong nhóm). Các liên kết giữa các nút được điều chỉnh để đảo ngược thứ tự của chúng. Cụ thể, `curr->next` được gán bằng `next->next` để liên kết với nút sau nút tiếp theo. `next->next` được gán bằng `prev->next` để liên kết với nút trước đó. Cuối cùng, `prev->next` được gán bằng `next` để liên kết với nút đảo ngược đầu tiên trong nhóm.
Sau khi hoàn thành vòng lặp bên trong, nhóm nút k đã được đảo ngược. Con trỏ `prev` và `curr` được cập nhật để trỏ đến nút cuối cùng của nhóm đã đảo ngược và nút tiếp theo của nhóm tiếp theo trong danh sách.
Cuối cùng, sau khi hoàn thành vòng lặp bên ngoài, danh sách liên kết đã được đảo ngược theo từng nhóm k nút. Con trỏ `dummy` không thay đổi, vì vậy ta trả về `dummy.next` là con trỏ đến danh sách liên kết đã đảo ngược.
Hàm `getLength` được sử dụng để tính độ dài của danh sách liên kết. Nó duyệt qua danh sách và đếm số lượng nút để trả về kết quả.
Ví dụ, nếu danh sách liên kết ban đầu là 1 -> 2 -> 3 -> 4 -> 5 và k = 2, sau khi áp dụng thuật toán, danh sách liên kết sẽ trở thành 2 -> 1 -> 4 -> 3 -> 5.
Giải thích thuật toán bằng Java
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || k == 1)
return head;
final int length = getLength(head);
ListNode dummy = new ListNode(0, head);
ListNode prev = dummy;
ListNode curr = head;
for (int i = 0; i < length / k; ++i) {
for (int j = 0; j < k - 1; ++j) {
ListNode next = curr.next;
curr.next = next.next;
next.next = prev.next;
prev.next = next;
}
prev = curr;
curr = curr.next;
}
return dummy.next;
}
private int getLength(ListNode head) {
int length = 0;
for (ListNode curr = head; curr != null; curr = curr.next)
++length;
return length;
}
}
Giải thích thuật toán bằng Python
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
if not head or k == 1:
return head
def getLength(head: ListNode) -> int:
length = 0
while head:
length += 1
head = head.next
return length
length = getLength(head)
dummy = ListNode(0, head)
prev = dummy
curr = head
for _ in range(length // k):
for _ in range(k - 1):
next = curr.next
curr.next = next.next
next.next = prev.next
prev.next = next
prev = curr
curr = curr.next
return dummy.next
0 / 5 - (0 Đánh Giá)