141. Linked List Cycle

Problem

Bài toán yêu cầu kiểm tra xem trong một linked list có tồn tại cycle hay không, tức là một node nào đó trỏ ngược lại một node trước đó trong danh sách hay không

Approach

Sử dụng two pointer: slow & fast

Mỗi bước lặp:

slow đi 1 bước (slow= slow.next)

fast đi 2 bước (fast = fast.next.next)

Nếu tồn tại chu trình, 2 pointers này sẽ gặp nhau tại một điểm nào đó trong chu trình

Nếu không có chu trình, pointer fast sẽ gặp null (tức là đi đến cuối danh sách)

💡

Thuật toán này còn gọi là Floyd’s Cycle-Finding Algorithm hoặc "Tortoise and Hare".

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 hasCycle(head: ListNode | null): boolean {
14    if(!head) return false;
15    
16    let slow = head;
17    let fast = head;
18    
19    while(fast && fast.next) {
20	    slow = slow.next;
21	    fast = fast.next.next;
22	    if(slow === fast) return true;
23    }
24    
25    return false
26};

Loading content...