Bài toán

Chúng ta cần xóa tất cả các node trong danh sách liên kết (linked list) có giá trị val cho trước. Sau khi xóa, chúng ta trả về head mới của danh sách.

Các bước thực hiện

Hiểu qua về danh sách liên kết (linked list):

Danh sách liên kết là một cấu trúc dữ liệu trong đó các phần tử (node) được nối với nhau bằng các liên kết (link).
Mỗi node bao gồm:

  • Một giá trị (value).
  • Một liên kết (next) trỏ tới node tiếp theo trong danh sách.
  • Node cuối cùng sẽ trỏ tới None, tức là không có node nào sau nó.

Ý tưởng giải thuật:

  • Chúng ta sẽ cần duyệt qua danh sách liên kết từ đầu đến cuối.
  • Nếu giá trị của node hiện tại là val, chúng ta sẽ bỏ qua node đó bằng cách thay đổi liên kết của node trước nó để trỏ tới node tiếp theo.
  • Nếu giá trị của node hiện tại khác val, chúng ta giữ nguyên liên kết và tiếp tục duyệt đến node tiếp theo.
  • Đặc biệt, nếu node đầu tiên (head) cũng có giá trị val, chúng ta cần cập nhật head để nó trỏ tới node tiếp theo cho đến khi head có giá trị khác val.

remove element linkedlist
Example
Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]

Triển khai:

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // Xử lý trường hợp đặc biệt: khi head có giá trị cần xóa
        while (head != null && head.val == val) {
            head = head.next; // Cập nhật head tới node tiếp theo
        }
        
        // Sử dụng con trỏ hiện tại để duyệt qua danh sách
        ListNode current = head;
        
        // Duyệt qua các node tiếp theo, dừng lại khi current là null hoặc current.next là null
        while (current != null && current.next != null) {
            if (current.next.val == val) {
                current.next = current.next.next; // Bỏ qua node có giá trị val
            } else {
                current = current.next; // Di chuyển tới node tiếp theo
            }
        }
        
        return head; // Trả về head mới của danh sách
    }
}


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

Giải thích:

Vòng lặp đầu tiên:

while (head != null && head.val == val): sẽ cập nhật head đến node tiếp theo nếu head hiện tại có giá trị bằng val. Vòng lặp này lặp lại cho đến khi gặp một head có giá trị khác val hoặc đến cuối danh sách.

Vòng lặp thứ hai:

current là một con trỏ bắt đầu từ head.
while (current != null && current.next != null) lặp qua tất cả các node trong danh sách:

  • Nếu current.next.val bằng val, chúng ta bỏ qua node đó bằng cách gán current.next cho current.next.next.
  • Nếucurrent.next.val không bằng val, chúng ta di chuyển con trỏ current tới node tiếp theo

Một chút thắc mắc:

Như chúng ta đã biết, toán tử “=” trong java nó là phép gán, biến current được gán bằng head, vậy tại sao khi chúng ta thực hiện thay đổi current thì giá trị của head lại bị thay đổi?

Để giải thích cụ thể, chúng ta sẽ xem xét bản chất của biến và cách chúng ta xử lý tham chiếu trong Java.

Tham chiếu trong Java
Trong Java, khi bạn gán một biến đối tượng, như current, bằng một đối tượng khác, như head, thì cả current và head đều trỏ đến cùng một vùng nhớ, tức là cùng một đối tượng danh sách liên kết. Vì vậy:

Khi chúng ta thay đổi thuộc tính của current (như current.next), chúng ta thực chất đang thay đổi vùng nhớ mà cả current và head đều trỏ tới.
-> Kết quả là, bất kỳ thay đổi nào với current cũng sẽ ảnh hưởng đến head, bởi cả hai đều trỏ tới cùng đối tượng ban đầu trong bộ nhớ.
Cụ thể trong code:

  • Ban đầu, chúng ta gán current = head, vậy current và head đều trỏ tới node đầu tiên.
  • Khi chúng ta thay đổi current.next (hoặc current = current.next), nó sẽ thay đổi liên kết của node mà head đang trỏ tới.
  • Nếu current chỉ di chuyển mà không thay đổi, head vẫn trỏ tới node đầu tiên như cũ. Nhưng khi current thay đổi next của node mà nó đang trỏ tới, chúng ta sẽ thấy sự thay đổi trong toàn bộ danh sách.

Ví dụ:
head -> [1] -> [2] -> [6] -> [3] -> [6] -> [4] -> null

Khi current đang trỏ tới node đầu tiên [1], vàcurrent.next là [2]. Nếu ta thay đổi current.next bằng cách làm current.next = current.next.next để bỏ qua node [6], thì danh sách liên kết mà head trỏ tới cũng sẽ bị thay đổi, vì head vẫn trỏ tới cùng danh sách mà current đang chỉnh sửa.