循环链表

1. 创建循环链表

1-单向链表 2-循环链表

循环链表的创建实际就是单向链表的尾节点指向头结点，最终形成一个环。

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define NOT_FOUND -1

/* ElemType类型根据实际情况而定，这里假设为int */
typedef int ElemType;
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;

/*线性结构使用顺序表的方式存储*/

//链表结构设计
typedef struct Node {
    ElemType data;
    struct Node *next;
} Node, *LinkList;

Status CreateList(LinkList *L) {
    ElemType elem;
    LinkList tail = NULL;
    while (1) {
        scanf("%d", &elem); // 输入数据
        if (elem == 0) break; // 输入0时结束
        if (*L == NULL) { // 表是空的时候
            *L = (LinkList)malloc(sizeof(Node)); // 创建表头
            if (*L == NULL) return ERROR; // 没创建出来报错
            (*L)->data = elem; // 存入数据
            tail = *L; // 尾节点，方便后续添加
        } else { // 表不为空
            tail->next = (LinkList)malloc(sizeof(Node)); // 创建新节点
            if (!tail->next) return ERROR; // 没创建出来报错
            tail->next->data = elem; // 存入数据
            tail = tail->next; // 之前的尾节点指向新节点
        }
    }
    tail->next = *L; // 形成环
    return OK;
}

2. 输出所有节点

Status ListTraverse(LinkList L)
{
    LinkList p = L; // 临时变量指向头节点
    do {
        printf("%4d ", p->data); // 打印临时节点的数据
        p = p->next; // 临时节点变为下一个节点
    } while (p != L); // 又回到表头，停止循环
    printf("\n");
    return OK;
}

3. 节点的插入与删除

其实不管是单向链表还是循环链表，增删操作核心都是找到前一个节点。

因为都是单向的，需要前一个节点的指向来获取插入位置的下一个节点。

3.1 插入

循环链表的插入

插入步骤：

1. 创建新节点
2. 找到前一个节点
3. 新节点指向前一个节点的后一个节点 ①
4. 前一个节点指向新节点 ②
5. 如果在头结点插入，还需要修改头结点的指向

Status ListInsert(LinkList *L, int loc, ElemType elem) {
    if (*L == NULL || loc < 1) return ERROR; // 空表，位置非法
    LinkList tmp = (LinkList)malloc(sizeof(Node)); // 1.创建新节点
    if (!tmp) return ERROR; // 没创建出来报错
    tmp->data = elem; // 存入数据
    LinkList target = *L; // 不管loc是多少，都是从头开始找
    if (loc == 1) {
        for (; target->next != *L; target = target->next); // 2.找到头结点的前一个节点(尾节点)
        *L = tmp; // 5.头结点变为新节点
    } else {
        int idx = 1;
        for (; target->next != *L && idx != loc - 1; target = target->next, ++idx); // 2.找到loc结点的前一个节点
        if (target->next == *L && idx != loc - 1) return ERROR; // 找了一圈了，还没到指定位置，越界
    }
    tmp->next = target->next; // 3.新节点指向前一个节点的下一个节点
    target->next = tmp; // 4.前一个节点指向新节点
    return OK;
}

3.2 删除

循环链表的删除

插入步骤：

1. 找到前一个节点
2. 临时指针指向被删除节点
3. 前一个节点指向被删除节点的后一个节点 ①
4. 释放被删除节点 ②
5. 如果在头结点删除，还需要修改头结点的指向下一个节点

Status ListDelete(LinkList *L, int loc, ElemType *elem) {
    if (*L == NULL || loc < 1) return ERROR; // 空表，位置非法
    LinkList tmp, target = *L; // 不管loc是多少，都是从头开始找
    if (loc == 1) {
        if ((*L)->next == *L) { // 如果只有1个节点
            free(*L);
            *L = NULL;
            return OK;
        };
        for (; target->next != *L; target = target->next); // 1.找到头结点的前一个节点(尾节点)
        *L = (*L)->next; // 5.头节点变为头节点的下一个节点
    } else {
        int idx = 1;
        for (; target->next != *L && idx != loc - 1; target = target->next, ++idx); // 1.找到loc结点的前一个节点
        if (target->next == *L && idx != loc - 1) return ERROR; // 找了一圈了，还没到指定位置，越界
    }
    tmp = target->next; // 2.tmp指向当前节点
    target->next = tmp->next; // 3.前一个节点指向当前节点的下一个节点
    *elem = tmp->data; // 获取被删除数据
    free(tmp); // 4.释放被删除节点
    return OK;
}

4. 查找元素并返回位置

和单向链表差不多，主要区别就是结束的判断。

• 单向链表结束的标志是尾节点的下一个节点为NULL
• 循环链表结束的标志是尾节点的下一个节点为头节点

int LocateElem(LinkList L, ElemType elem)
{
    if (L == NULL) return NOT_FOUND; // 空表
    int i = 1;
    LinkList p = L; // 从表头开始找
    do {
        if (p->data == elem) return i; // 找到直接返回
        i++;
        p = p->next;
    } while (p != L); // 只找一圈
    return NOT_FOUND;
}

5. 约瑟夫环(杀人游戏算法)

已知 n 个人（分别用编号 1，2，3，…，n 表示）围坐在一张圆桌周围，从编号为 k 的人开始顺时针报数，数到 m 的那个人出列；他的下一个人又从 1 开始，还是顺时针开始报数，数到 m 的那个人又出列；依次重复下去，直到圆桌上剩余一个人。

5.1 问题分析

很明显这是一个环，我们需要用循环链表解决。

要解决问题有几个阶段：

1. 创建循环链表
2. 找到开始的序号
3. 开始执行报数，直到只剩一个人

用到的循环链表知识：

1. 循环链表的创建
2. 循环链表元素的查找
3. 循环链表的节点的删除

5.2 代码实现

Status josephKill(int n, int start, int m)
{
    if (n <= 0 || start < 1 || m < 1 || start > n)
        return ERROR;

    // 1.创建循环链表
    LinkList head = (LinkList)malloc(sizeof(Node));
    head->data = 1;
    if (head == NULL) return ERROR;
    LinkList target = head;
    for (int i = 2; i <= n; i++) {
        target->next = (LinkList)malloc(sizeof(Node));
        if (target->next == NULL) return ERROR;
        target->next->data = i;
        target = target->next;
    }
    target->next = head;

    // 2.找到开始序号的人
    target = head;
    do {
        if (target->data == start) break; // 找到对应的序号
        target = target->next;
    } while (target != head);
    if (target == head && target->data != start) return ERROR; // 找了一圈，没有找到对应序号

    // 3.循环到只剩一个人
    int i;
    LinkList tmp = NULL;
    while (target->next != target) {
        for (i = 1; i < m; i++) {
            tmp = target; // 记录前一个节点，方便删除和释放
            target = target->next; // 向后移动一个节点
        }
        tmp->next = target->next; // 前一个节点指向当前节点的下一个节点
        printf("%d was killed.\n", target->data);
        free(target); // 释放被删除节点
        // 从下一个节点开始
        target = tmp->next;
    }
    printf("%d survived!\n", target->data);
    return OK;
}

int main(int argc, const char * argv[]) {   
    josephKill(5, 3, 2);
}

//输出
4 was killed.
1 was killed.
3 was killed.
2 was killed.
5 survived!
Program ended with exit code: 0

6. 循环链表的逆序

因为是单向链表：

• 断开节点前需要引用下一个节点，要不然就找不到了。
• 单向链表没法直接找到前一个节点，所以需要一个额外的引用。

Status ListReverse(LinkList *L) {
    if (L == NULL) return ERROR; // 空表
    LinkList prev, current, next;
    prev = *L;
    current = prev->next;
    next = current->next;
    while (current != *L) { // 当current为头结点时结束，再移动就找不到尾节点了
        current->next = prev; // 指针反向
        // 依次移动节点
        prev = current;
        current = next;
        next = next->next;
    }
    current->next = prev; // current为头结点，但还没有反向，所以先反向
    *L = prev; // 头结点逆序后应为原来的尾节点
    return OK;
}

7. 循环链表倒数第k个数

核心思想是两个指针，保证2个指针间隔为 k，后面的指针到头的时候，另一个指针指向倒数第 k 个数。

// 循环链表倒数第k个元素
Status ListLocateKBackwards(LinkList L, int k, ElemType *elem) {
    if (L == NULL) return ERROR; // 空表
    LinkList target, tmp;
    target = L;
    tmp = L->next;
    // 移动tmp使得两个指针间隔k
    int i = 1;
    for (; i < k && tmp != L; tmp = tmp->next, i++);
    if (tmp == L && i < k) return ERROR;
    // tmp走到头的时候，倒数第k个节点被target指针指向
    do {
        target = target->next;
        tmp = tmp->next;
    } while (tmp != L);
    *elem = target->data;
    return OK;
}