Bài 19 Leetcode: Remove Nth Node From End of List

Đề bài:

Cho head của một danh sách liên kết, loại bỏ nút n ^th từ cuối danh sách và trả về đầu của danh sách.

Ví dụ 1:

Remove Nth Node From End of List
Remove Nth Node From End of List
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Ví dụ 2:

Input: head = [1], n = 1
Output: []

Ví dụ 3:

Input: head = [1,2], n = 1
Output: [1]

Ràng buộc:

  • Số lượng nút trong danh sách là sz.
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

Giải thích thuật toán bằng C++

class Solution {
 public:
  ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* slow = head;
    ListNode* fast = head;

    while (n--)
      fast = fast->next;
    if (fast == nullptr)
      return head->next;

    while (fast->next) {
      slow = slow->next;
      fast = fast->next;
    }
    slow->next = slow->next->next;

    return head;
  }
};

Đây là một phương thức trong một lớp được gọi là `Solution`. Phương thức này được sử dụng để loại bỏ nút thứ `n` từ cuối danh sách liên kết và trả về đầu của danh sách.

Dưới đây là cách thuật toán hoạt động:

1. Phương thức `removeNthFromEnd` nhận đầu vào là một con trỏ `head` trỏ đến đầu của danh sách và một số nguyên `n` đại diện cho vị trí của nút cần loại bỏ.

2. Khởi tạo hai con trỏ `slow` và `fast` và đều trỏ đến `head`.

3. Sử dụng vòng lặp while để di chuyển con trỏ `fast` `n` bước tiến phía trước. Điều này đảm bảo rằng khoảng cách giữa `fast` và `slow` là `n`.

4. Kiểm tra nếu `fast` trỏ đến nullptr, điều này có nghĩa là `n` bằng đúng số nút trong danh sách. Trong trường hợp này, ta cần loại bỏ nút đầu tiên của danh sách và trả về con trỏ `head->next`.

5. Sử dụng vòng lặp while để di chuyển cả `slow` và `fast` cùng một lúc cho đến khi `fast` trỏ đến nút cuối cùng của danh sách. Khi vòng lặp kết thúc, `slow` sẽ trỏ đến nút trước nút cần loại bỏ.

6. Thay đổi liên kết bằng cách gán `slow->next` bằng `slow->next->next`. Điều này loại bỏ nút cần loại bỏ khỏi danh sách.

7. Trả về con trỏ `head`, đại diện cho danh sách đã được chỉnh sửa.

Thuật toán này sử dụng hai con trỏ `slow` và `fast` để duyệt qua danh sách liên kết. Con trỏ `fast` được di chuyển `n` bước tiến phía trước so với con trỏ `slow`, điều này đảm bảo khoảng cách giữa chúng là `n`. Khi `fast` đến cuối danh sách, `slow` sẽ trỏ đến nút trước nút cần loại bỏ, do đó ta có thể thay đổi liên kết để loại bỏ nút đó khỏi danh sách.

Giải thích thuật toán bằng Java

class Solution {
  public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode slow = head;
    ListNode fast = head;

    while (n-- > 0)
      fast = fast.next;
    if (fast == null)
      return head.next;

    while (fast.next != null) {
      slow = slow.next;
      fast = fast.next;
    }
    slow.next = slow.next.next;

    return head;
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
    slow = head
    fast = head

    for _ in range(n):
      fast = fast.next
    if not fast:
      return head.next

    while fast.next:
      slow = slow.next
      fast = fast.next
    slow.next = slow.next.next

    return head

Leave a Reply

Your email address will not be published. Required fields are marked *

PHP Code Snippets Powered By : XYZScripts.com
.
.
.
.