19. Remove Nth Node From End of List

Problem

Bài toán yêu cầu xóa node thứ n tính từ cuối danh sách Linked List và return về head của danh sách mới

Approach

Sử dụng 2 pointer: fast và slow

Đầu tiên, cho fast chạy trước n bước

Sau đó, di chuyển cả fast và slow cùng lúc cho đến khi fast đến cuối danh sách

Khi đó slow sẽ đứng ngay trước node cần xóa. Chỉ cần bỏ qua node này bằng cách cập nhật slow.next

Để xử lý trường hợp xóa node đầu tiên, nên dùng một dummy node đứng trước head

Solution

typescripttypescript

1/**
2 * Definition for singly-linked list.
3 * class ListNode {
4 *     val: number
5 *     next: ListNode | null
6 *     constructor(val?: number, next?: ListNode | null) {
7 *         this.val = (val===undefined ? 0 : val)
8 *         this.next = (next===undefined ? null : next)
9 *     }
10 * }
11 */
12
13function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
14	const dummy = new ListNode(0, head);
15	let fast: ListNode | null = dummy;
16	let slow: ListNode | null = dummy;
17	for(let i = 0; i < n; i++) {
18		if(fast) fast = fast.next;
19	}
20	
21	while(fast && fast.next) {
22		fast = fast.next;
23		slow = slow.next;
24	}
25	
26	if(slow && slow.next) {
27		slow.next = slow.next.next
28	}
29	
30	return dummy.next;
31};

💡

Giải thích chi tiết

Dummy node giúp đơn giản hóa việc xóa node đầu tiên của danh sách

Hai pointer fast và slow đảm bảo sau khi fast chạy n bước, khi fast đến cuối thì slow.next chính là node cần xóa

💡

Tại sao lại cần di chuyển fast lên n bước

Khi di chuyển pointer fast lên n bước là để tạo ra khoảng cách đúng bằng n node giữa hai con trỏ fast và slow . Sau đó, khi cả hai pointer cùng di chuyển từng bước một cho đến khi fast đến cuối danh sách, thì lúc đó pointer slow sẽ đứng ngay trước node cần xóa (node thứ n từ cuối)

Nhờ vậy, bạn chỉ cần cập nhật slow.next để bỏ qua node cần xóa

Kỹ thuật này giúp xác định vị trí node cần xóa mà không cần phải duyệt danh sách hai lần hoặc phải tính tổng số node trước, đảm bảo thuật toán chỉ duyệt qua danh sách một lần với độ phức tạp O(L).

Loading content...

1/** 2 * Definition for singly-linked list. 3 * class ListNode { 4 * val: number 5 * next: ListNode | null 6 * constructor(val?: number, next?: ListNode | null) { 7 * this.val = (val===undefined ? 0 : val) 8 * this.next = (next===undefined ? null : next) 9 * } 10 * } 11 */ 12 13function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null { 14 const dummy = new ListNode(0, head); 15 let fast: ListNode | null = dummy; 16 let slow: ListNode | null = dummy; 17 for(let i = 0; i < n; i++) { 18 if(fast) fast = fast.next; 19 } 20 21 while(fast && fast.next) { 22 fast = fast.next; 23 slow = slow.next; 24 } 25 26 if(slow && slow.next) { 27 slow.next = slow.next.next 28 } 29 30 return dummy.next; 31};