8、循环链表：单向循环链表、双向循环链表、约瑟夫环问题

各位同学，今天我们来聊聊循环链表。说实话，我第一次接触这个概念时，觉得它就是个「把尾巴咬住的蛇」。但后来在项目中用多了，才发现它比普通链表灵活得多。

循环链表，说白了就是让链表的最后一个节点不再指向 NULL，而是指回头节点。这样一来，整个链表就变成了一个环。你从任何一个节点出发，都能遍历整个链表。嗯，这个特性在某些场景下非常有用。

单向循环链表

单向循环链表是最基础的形式。它的每个节点只有一个 next 指针，但尾节点的 next 指向头节点。

我个人的习惯是，在实现单向循环链表时，会保留一个头指针。但要注意，这个头指针指向的节点，其实也是环中的一个普通节点。你想想看，如果头指针指向一个「哨兵节点」，那遍历时就要小心别死循环了。

来看一个简单的创建和遍历示例：

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

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

// 创建单向循环链表（尾插法）
Node* createCircularList(int arr[], int n) {
    if (n <= 0) return NULL;
    
    Node *head = (Node*)malloc(sizeof(Node));
    head->data = arr[0];
    head->next = head;  // 先指向自己
    Node *tail = head;
    
    for (int i = 1; i < n; i++) {
        Node *newNode = (Node*)malloc(sizeof(Node));
        newNode->data = arr[i];
        newNode->next = head;  // 新节点指向头
        tail->next = newNode;  // 尾节点指向新节点
        tail = newNode;        // 更新尾节点
    }
    return head;
}

// 遍历单向循环链表
void traverse(Node *head) {
    if (head == NULL) return;
    Node *p = head;
    do {
        printf("%d ", p->data);
        p = p->next;
    } while (p != head);  // 回到头就停止
    printf("\n");
}

这里有个细节：遍历时我用的是 do-while 而不是 while。为什么？因为如果用 while，第一次循环条件 p != head 就不成立，直接跳过了。嗯，这个小坑我踩过。

双向循环链表

双向循环链表就更灵活了。每个节点有 prev 和 next 两个指针，头节点的 prev 指向尾节点，尾节点的 next 指向头节点。

我在项目中用过双向循环链表来实现一个「最近使用列表」。用户每次操作一个功能，我就把这个节点移到链表头部。因为是双向的，删除和插入都只需要 O(1) 时间。

双向循环链表的节点定义：

typedef struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode;

// 在双向循环链表头部插入
void insertAtHead(DNode **head, int data) {
    DNode *newNode = (DNode*)malloc(sizeof(DNode));
    newNode->data = data;
    
    if (*head == NULL) {
        newNode->prev = newNode;
        newNode->next = newNode;
        *head = newNode;
        return;
    }
    
    DNode *tail = (*head)->prev;
    newNode->next = *head;
    newNode->prev = tail;
    (*head)->prev = newNode;
    tail->next = newNode;
    *head = newNode;  // 更新头指针
}

你想想看，双向循环链表的优势在哪？从任意节点出发，向前向后都能遍历。而且查找某个节点的前驱节点，不需要从头遍历。这在某些算法中能省不少时间。

约瑟夫环问题

约瑟夫环问题，是循环链表的经典应用。故事是这样的：N 个人围成一圈，从第一个人开始报数，报到 M 的人出列，然后从下一个人重新报数，直到所有人出列。问出列顺序。

我第一次看到这个问题时，觉得用循环链表实现最直观。因为「围成一圈」本身就是循环链表的结构。

来看完整实现：

// 约瑟夫环问题求解
void josephus(int n, int m) {
    // 创建循环链表：1 到 n
    Node *head = NULL, *tail = NULL;
    for (int i = 1; i <= n; i++) {
        Node *newNode = (Node*)malloc(sizeof(Node));
        newNode->data = i;
        if (head == NULL) {
            head = newNode;
            head->next = head;
            tail = head;
        } else {
            newNode->next = head;
            tail->next = newNode;
            tail = newNode;
        }
    }
    
    // 开始报数出列
    Node *p = head;
    Node *prev = tail;  // p 的前驱节点
    int count = 0;
    
    while (p->next != p) {  // 只剩一个节点时停止
        count++;
        if (count == m) {
            // 出列
            printf("%d 出列\n", p->data);
            prev->next = p->next;
            free(p);
            p = prev->next;
            count = 0;
        } else {
            prev = p;
            p = p->next;
        }
    }
    printf("最后剩下: %d\n", p->data);
    free(p);
}

这段代码里，我用了 prev 指针来记录 p 的前驱节点。为什么？因为单向循环链表删除节点时，需要知道前驱节点才能修改 next 指针。我曾经在写这段代码时，忘了维护 prev，结果链表断开了，调试了半天才发现。

三种结构的对比

特性	单向循环链表	双向循环链表	普通单向链表
遍历方向	单向	双向	单向
尾节点指向	头节点	头节点	NULL
从头到尾遍历	需要判断回到头	需要判断回到头	判断 NULL
删除节点效率	需要前驱节点	不需要前驱节点	需要前驱节点
内存占用	较小	较大（多一个指针）	最小

从表中可以看出，双向循环链表虽然内存占用大一些，但操作更灵活。我个人在需要频繁插入删除的场景下，优先选择双向循环链表。

知识体系结构图

下面这张图展示了循环链表的核心知识点和它们之间的关系：

从图中可以看出，三种结构都围绕「环」这个核心概念展开。单向循环链表是最基础的，双向循环链表是增强版，约瑟夫环则是经典应用。

最后说一句，循环链表虽然看起来比普通链表复杂，但一旦理解了「环」的本质，用起来其实很顺手。你想想看，很多现实问题本身就是环形的——比如轮询调度、游戏中的回合制、消息队列的循环缓冲区。用循环链表来建模，代码会非常自然。

---

公众号:蓝海资料掘金营，微信deep3321