Đảo ngược và hai con trỏ

/* Đảo ngược tại chỗ. O(n) thời gian, O(1) bộ nhớ. */
void list_dao_nguoc(List *l)
{
    Node *truoc = NULL;
    Node *hien  = l->head;

    l->tail = l->head;               /* đầu cũ sẽ thành cuối mới */

    while (hien != NULL) {
        Node *sau = hien->next;      /* 1. LƯU nút kế trước khi mất nó */

        hien->next = truoc;          /* 2. ĐẢO hướng mũi tên */
        truoc      = hien;           /* 3. TIẾN truoc */
        hien       = sau;            /* 4. TIẾN hien */
    }

    l->head = truoc;                 /* truoc dừng ở nút cuối cũ */
}

/* Đảo ngược đệ quy. Trả về đầu mới của đoạn đã đảo. */
static Node *dao_de_quy(Node *hien, Node *truoc)
{
    if (hien == NULL) return truoc;      /* hết danh sách, truoc là đầu mới */

    Node *sau = hien->next;

    hien->next = truoc;

    return dao_de_quy(sau, hien);        /* đệ quy đuôi */
}

void list_dao_nguoc_de_quy(List *l)
{
    l->tail = l->head;
    l->head = dao_de_quy(l->head, NULL);
}

/* Đảo phần đuôi trước, rồi nối nút hiện tại vào cuối.
   Đây KHÔNG phải đệ quy đuôi, nên không tối ưu thành vòng lặp được. */
static Node *dao_khong_duoi(Node *hien)
{
    if (hien == NULL || hien->next == NULL) return hien;

    Node *dau_moi = dao_khong_duoi(hien->next);

    hien->next->next = hien;      /* nút kế giờ trỏ ngược về hien */
    hien->next       = NULL;

    return dau_moi;
}

/* Trả về nút giữa. Với n chẵn thì trả về nút thứ n/2, tức nút
   đầu của nửa sau. Trả về NULL nếu danh sách rỗng. */
Node *list_giua(const List *l)
{
    Node *cham  = l->head;
    Node *nhanh = l->head;

    while (nhanh != NULL && nhanh->next != NULL) {
        cham  = cham->next;
        nhanh = nhanh->next->next;
    }

    return cham;
}

/* Trả về 1 nếu có chu trình, 0 nếu không. */
int list_co_chu_trinh(const List *l)
{
    Node *cham  = l->head;
    Node *nhanh = l->head;

    while (nhanh != NULL && nhanh->next != NULL) {
        cham  = cham->next;
        nhanh = nhanh->next->next;

        if (cham == nhanh) return 1;      /* gặp nhau, chắc chắn có vòng */
    }

    return 0;                            /* nhanh ra khỏi danh sách */
}

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int data; struct Node *next; } Node;

int co_chu_trinh(Node *head)
{
    Node *cham = head, *nhanh = head;

    while (nhanh && nhanh->next) {
        cham  = cham->next;
        nhanh = nhanh->next->next;

        if (cham == nhanh) return 1;
    }

    return 0;
}

int main(void)
{
    Node *n[6];

    for (int i = 0; i < 6; ++i) {
        n[i] = malloc(sizeof *n[i]);

        if (n[i] == NULL) return 1;

        n[i]->data = i;
        n[i]->next = NULL;
    }

    for (int i = 0; i < 5; ++i) n[i]->next = n[i + 1];

    printf("danh sach thang : %d\n", co_chu_trinh(n[0]));

    n[5]->next = n[2];                /* tạo chu trình quay về nút 2 */

    printf("co chu trinh    : %d\n", co_chu_trinh(n[0]));

    n[5]->next = NULL;                /* cắt vòng để giải phóng được */

    for (int i = 0; i < 6; ++i) free(n[i]);

    return 0;
}

/* Trả về nút mà chu trình bắt đầu, hoặc NULL nếu không có chu trình. */
Node *list_dau_chu_trinh(const List *l)
{
    Node *cham = l->head, *nhanh = l->head;

    /* Giai đoạn 1: tìm điểm gặp nhau */
    while (nhanh != NULL && nhanh->next != NULL) {
        cham  = cham->next;
        nhanh = nhanh->next->next;

        if (cham == nhanh) break;
    }

    if (nhanh == NULL || nhanh->next == NULL) return NULL;   /* không có vòng */

    /* Giai đoạn 2: đưa một con về đầu, cùng đi MỘT nhịp */
    cham = l->head;

    while (cham != nhanh) {
        cham  = cham->next;
        nhanh = nhanh->next;
    }

    return cham;      /* điểm bắt đầu chu trình */
}