Bài tập về danh sách liên kết đơn

int phan_tu_n2(Node * ds)

int phan_tu_k_tu_cuoi(Node * ds, int k)

 Node * node_bat_dau_chu_trinh(Node * head)

if (ds) {
    Node * walker = ds;
    Node * runner = ds;
    while (runner->next && runner->next->next) {
        walker = walker->next;
        runner = runner->next->next;
    }
        return walker;
}
return 0;

Node * last = ds;
for (int i = 0; last && i < k; last = last->next, ++i);
for (Node * i = ds; last; last = last->next, i = i->next)
    if (!last->next)
        return i;
return 0;

Giả sử có linked list với node E là cycle entry và X là node mà 2 pointers bắt kịp nhau ở trong cycle. Gọi:
- H: khoảng cách từ head tới E.
- D: khoảng cách từ E tới X.
- L: cycle length.
                 _____
                /     \
head_____H______E      \
                \      /
                 X____/
Tại X, walker đã đi đc quãng đg` là H + D, còn faster đi đc quãng đg` là 2(H + D). Nếu faster đã đi quanh cycle đc n vòng thì ta có:
2H + 2D = H + D + nL, so H + D = nL, H = nL - D.
Bởi vậy, sau khi biết đc có chu trình, cho 2 pointers chạy: một từ head, một từ X thì 2 pointers này phải gặp nhau ở E.

if (head == 0) return 0;
ListNode * walker = head, * runner = head;
bool hasCycle = 0;
while (runner->next != 0 && runner->next->next != 0) {
    walker = walker->next;
    runner = runner->next->next;
    if (walker == runner) {
        hasCycle = 1;
        break;
    }
}
if (!hasCycle) return 0;
while (head != walker) {
    head = head->next;
    walker = walker->next;
}
return head;