C语言-实验11-链表

Note

本系列将以一个学习者的眼光，从零基础一步一步学会最基础的C语言编程，本文将讲解C语言第十一个板块：链表。

在C语言中，数组的长度在定义时就已固定，无法动态扩容/缩容；而链表通过结构体+动态内存分配（malloc/free）实现，每个节点独立分配内存，节点间通过指针连接，可灵活增删节点。链表的核心是节点结构体定义和动态内存管理，本文重点讲解单链表的创建、顺序插入、倒序插入等核心操作。

动态内存分配#

函数原型	功能说明	关键特性
`void *malloc(unsigned int size);`	分配 `size`字节的连续堆内存	1. 内存未初始化 2. 成功返回内存首地址，失败返回 `NULL`
`void *calloc(unsigned int n, unsigned int size);`	分配 `n`个大小为 `size`字节的连续堆内存	1. 内存自动初始化为0 2. 等价于 `malloc(n*size) + 内存清零` 3. 失败返回 `NULL`
`void realloc(void p_block, unsigned int size);`	调整已分配内存块的大小	1.`p_block`为 `malloc/calloc`返回的地址 2. 可扩容/缩容，可能迁移内存块 3. 失败返回 `NULL`，原内存块保留
`void free(void *p_block);`	释放已分配的堆内存	1.`p_block`必须是动态分配的地址 2. 释放后指针需置 `NULL`，避免野指针 3. 不能重复释放/释放栈内存

链表基础#

1. 链表节点的定义#

链表的核心是节点结构体，每个节点包含两部分：数据域和 指针域。

2. 核心语法#

1
// 1. 定义链表节点结构体
2
struct ListNode {
3
    int data;// 数据域：存储节点数据
4
    struct ListNode *next;  // 指针域：指向下一个节点的指针
5
};
6

7
// 2. 动态内存分配函数
8
// 分配新节点内存：malloc，返回void*，需强制类型转换
9
struct ListNode *createNode(int data) {
10
    // 分配节点内存
11
    struct ListNode *newNode = (struct ListNode *)malloc(sizeof(struct ListNode));
12
    // 内存分配失败判断
13
    if (newNode == NULL) {
14
        printf("内存分配失败！\n");
15
        exit(1);
16
    }
17
    // 初始化节点数据和指针
18
    newNode->data = data;
19
    newNode->next = NULL; // 新节点默认指向NULL
20
    return newNode;
21
}
22
// 3. 遍历链表
23
void traverseList(struct ListNode *head) {
24
    struct ListNode *p = head;
25
    if (p == NULL) {
26
        printf("链表为空！\n");
27
        return;
28
    }
29
    printf("链表节点：");
30
    while (p != NULL) {
31
        printf("%d ", p->data);
32
        p = p->next;
33
    }
34
    printf("\n");
35
}

链表的插入操作#

链表插入的核心是调整指针指向，分为顺序插入（按数据大小/先后插入到链表尾部）和倒序插入（插入到链表头部，新节点成为新头节点）。

1. 倒序插入（头插法）#

核心逻辑：新节点的 next指向原头节点，再将头指针指向新节点，最终链表顺序与插入顺序相反。

1
// 倒序插入：新节点插入到链表头部
2
struct ListNode *insertReverse(struct ListNode *head, int data) {
3
    // 1. 创建新节点
4
    struct ListNode *newNode = createNode(data);
5
    // 2. 新节点next指向原头节点
6
    newNode->next = head;
7
    // 3. 头指针指向新节点
8
    head = newNode;
9
    return head; // 返回新的头节点
10
}

2. 顺序插入（尾插法）#

核心逻辑：找到链表最后一个节点（next为NULL），将最后一个节点的 next指向新节点，最终链表顺序与插入顺序一致。

1
// 顺序插入：新节点插入到链表尾部
2
struct ListNode *insertOrder(struct ListNode *head, int data) {
3
    // 1. 创建新节点
4
    struct ListNode *newNode = createNode(data);
5
    // 2. 链表为空时，新节点直接作为头节点
6
    if (head == NULL) {
7
        head = newNode;
8
        return head;
9
    }
10
    // 3. 找到链表最后一个节点
11
    struct ListNode *p = head;
12
    while (p->next != NULL) {
13
        p = p->next;
14
    }
15
    // 4. 最后一个节点的next指向新节点
16
    p->next = newNode;
17
    return head; // 头节点不变，返回原头
18
}

注：先后顺序为绿色、蓝色、黄色、紫色

链表的查找操作#

1.按值查找结点#

核心逻辑：从链表头节点开始遍历，逐个比对节点数据域与目标值，找到则返回该节点指针；遍历结束未找到则返回 NULL。

1
// 按值查找：返回第一个数据等于target的节点指针，未找到返回NULL
2
struct ListNode *findNode(struct ListNode *head, int target) {
3
    // 1. 空链表直接返回NULL
4
    if (head == NULL) {
5
        return NULL;
6
    }
7
    // 2. 遍历链表
8
    struct ListNode *p = head;
9
    while (p != NULL) {
10
        // 3. 找到目标节点，返回指针
11
        if (p->data == target) {
12
            return p;
13
        }
14
        // 4. 未找到则移动到下一个节点
15
        p = p->next;
16
    }
17
    // 5. 遍历结束未找到，返回NULL
18
    return NULL;
19
}

2.按位置查找结点#

核心逻辑：按索引（从 0 开始）查找节点，遍历过程中计数，计数等于目标索引则返回该节点；索引越界返回 NULL。

1
// 按位置查找：返回索引为index的节点指针（索引从0开始），越界返回NULL
2
struct ListNode *findNodeByIndex(struct ListNode *head, int index) {
3
    // 1. 空链表或负索引直接返回NULL
4
    if (head == NULL || index < 0) {
5
        return NULL;
6
    }
7
    // 2. 遍历链表并计数
8
    struct ListNode *p = head;
9
    int count = 0;
10
    while (p != NULL) {
11
        // 3. 找到目标索引，返回指针
12
        if (count == index) {
13
            return p;
14
        }
15
        count++;
16
        p = p->next;
17
    }
18
    // 4. 索引越界，返回NULL
19
    return NULL;
20
}

链表的删除操作#

1.按值删除结点#

核心逻辑：

步骤1：找到待删节点的前驱节点（若删除头节点则无前驱，直接更新头指针）；
步骤2：调整前驱节点的next指向待删节点的后继节点；
步骤3：释放待删节点的内存，避免内存泄漏。

1
// 按值删除：删除第一个数据等于target的节点，返回新的头节点
2
struct ListNode *deleteNode(struct ListNode *head, int target) {
3
    // 1. 空链表直接返回NULL
4
    if (head == NULL) {
5
        return NULL;
6
    }
7

8
    struct ListNode *p = head;
9
    struct ListNode *prev = NULL; // 保存前驱节点
10

11
    // 2. 处理删除头节点的情况
12
    if (p->data == target) {
13
        head = p->next; // 头指针指向原头节点的下一个节点
14
        free(p);        // 释放原头节点内存
15
        p = NULL;
16
        return head;
17
    }
18

19
    // 3. 遍历查找待删节点及其前驱
20
    while (p != NULL && p->data != target) {
21
        prev = p;
22
        p = p->next;
23
    }
24

25
    // 4. 未找到目标节点，返回原头节点
26
    if (p == NULL) {
27
        return head;
28
    }
29

30
    // 5. 找到目标节点，调整前驱节点指针
31
    prev->next = p->next;
32
    // 6. 释放待删节点内存
33
    free(p);
34
    p = NULL;
35

36
    return head; // 返回头节点（未删除头节点则不变）
37
}

逆置单链表#

1.迭代法逆置单链表#

核心逻辑：用三个指针（前驱prev、当前curr、后继next）遍历链表，逐个将当前节点的next指向前驱，最终prev指向新头节点。

1
// 迭代法逆置单链表，返回新头节点
2
struct ListNode *reverseList(struct ListNode *head) {
3
    struct ListNode *prev = NULL;  // 前驱节点初始为空
4
    struct ListNode *curr = head;  // 当前节点从原头节点开始
5
    struct ListNode *next = NULL;  // 保存后继节点
6

7
    while (curr != NULL) {
8
        next = curr->next;  // 先保存当前节点的后继，避免断链
9
        curr->next = prev;  // 反转当前节点的指针
10
        prev = curr;        // 前驱指针后移
11
        curr = next;        // 当前指针后移
12
    }
13
    return prev;  // 原尾节点变为新头节点
14
}

单链表归并#

1.归并两个升序单链表#

核心逻辑：创建哑节点作为新链表头，用指针遍历两个原链表，每次选择数值较小的节点接入新链表，最后拼接剩余节点。

1
// 归并两个升序链表，返回新的升序链表头
2
struct ListNode *mergeList(struct ListNode *l1, struct ListNode *l2) {
3
    // 创建哑节点（简化头节点处理）
4
    struct ListNode dummy = {0, NULL};
5
    struct ListNode *p = &dummy;
6

7
    // 同时遍历两个链表，选择较小节点接入
8
    while (l1 != NULL && l2 != NULL) {
9
        if (l1->data <= l2->data) {
10
            p->next = l1;
11
            l1 = l1->next;
12
        } else {
13
            p->next = l2;
14
            l2 = l2->next;
15
        }
16
        p = p->next;
17
    }
18

19
    // 拼接剩余节点（其中一个链表已遍历完）
20
    p->next = (l1 != NULL) ? l1 : l2;
21

22
    return dummy.next;  // 哑节点的next为新链表头
23
}

单链表拆分#

1.按数值奇偶拆分单链表#

核心逻辑：创建两个哑节点分别作为奇偶链表头，遍历原链表，将奇数数值节点接入奇数链表，偶数数值节点接入偶数链表。

1
// 按数值奇偶拆分链表，oddHead为奇数链表头，evenHead为偶数链表头
2
void splitList(struct ListNode *head, struct ListNode **oddHead, struct ListNode **evenHead) {
3
    // 初始化两个哑节点
4
    struct ListNode oddDummy = {0, NULL};
5
    struct ListNode evenDummy = {0, NULL};
6
    struct ListNode *oddP = &oddDummy;  // 奇数链表指针
7
    struct ListNode *evenP = &evenDummy;// 偶数链表指针
8

9
    // 遍历原链表，按数值奇偶拆分
10
    while (head != NULL) {
11
        if (head->data % 2 == 1) {  // 奇数
12
            oddP->next = head;
13
            oddP = oddP->next;
14
        } else {  // 偶数
15
            evenP->next = head;
16
            evenP = evenP->next;
17
        }
18
        head = head->next;
19
    }
20

21
    // 终止两个子链表
22
    oddP->next = NULL;
23
    evenP->next = NULL;
24

25
    // 返回两个子链表头（跳过哑节点）
26
    *oddHead = oddDummy.next;
27
    *evenHead = evenDummy.next;
28
}

循环链表#

1.创建循环链表#

1
// 尾插法创建循环链表，返回头节点
2
struct ListNode *createCircularList(int arr[], int n) {
3
    if (n == 0) return NULL;
4

5
    // 创建头节点
6
    struct ListNode *head = createNode(arr[0]);
7
    struct ListNode *p = head;
8

9
    // 尾插剩余节点
10
    for (int i = 1; i < n; i++) {
11
        p->next = createNode(arr[i]);
12
        p = p->next;
13
    }
14

15
    // 尾节点指向头节点，形成循环
16
    p->next = head;
17
    return head;
18
}

约瑟夫环问题#

1.约瑟夫环求解#

核心逻辑：构建循环链表，用指针遍历，数到目标步数时删除当前节点，调整指针形成新循环，直至链表只剩一个节点。

1
// 约瑟夫环：n个节点，每次数m步淘汰，返回最后剩余节点的数值
2
int josephus(int n, int m) {
3
    if (n == 1) return 1;  // 只有1个节点，直接返回
4

5
    // 1. 构建n个节点的循环链表
6
    struct ListNode *head = createNode(1);
7
    struct ListNode *p = head;
8
    for (int i = 2; i <= n; i++) {
9
        p->next = createNode(i);
10
        p = p->next;
11
    }
12
    p->next = head;  // 形成循环
13

14
    // 2. 模拟淘汰过程
15
    struct ListNode *prev = p;  // 前驱节点初始为尾节点
16
    p = head;                   // 当前节点初始为头节点
17
    while (p->next != p) {      // 只剩1个节点时终止
18
        // 数m步（移动m-1次）
19
        for (int i = 1; i < m; i++) {
20
            prev = p;
21
            p = p->next;
22
        }
23
        // 删除当前节点
24
        prev->next = p->next;
25
        free(p);
26
        p = prev->next;  // 从下一个节点继续数
27
    }
28

29
    int res = p->data;
30
    free(p);  // 释放最后一个节点
31
    return res;
32
}

示例#

1.链表节点定义+创建节点#

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
struct ListNode {
5
    int data;
6
    struct ListNode *next;
7
};
8

9

10
struct ListNode *createNode(int data) {
11

12
    struct ListNode *newNode = (struct ListNode *)malloc(sizeof(struct ListNode));
13

14
    if (newNode == NULL) {
15
        printf("内存分配失败！\n");
16
        exit(1);
17
    }
18

19
    newNode->data = data;
20
    newNode->next = NULL;
21
    return newNode;
22
}
23

24
int main() {
25
    struct ListNode *node = createNode(10);
26
    printf("节点数据：%d\n", node->data);
27
    free(node);
28
    node = NULL;
29
    return 0;
30
}

输出：
1
节点数据：10

2.尾插法（顺序插入）#

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
struct ListNode {
5
    int data;
6
    struct ListNode *next;
7
};
8

9
struct ListNode *createNode(int data) {
10
    struct ListNode *newNode = (struct ListNode *)malloc(sizeof(struct ListNode));
11
    if (newNode == NULL) { exit(1); }
12
    newNode->data = data;
13
    newNode->next = NULL;
14
    return newNode;
15
}
16

17
struct ListNode *insertOrder(struct ListNode *head, int data) {
18
    struct ListNode *newNode = createNode(data);
19
    if (head == NULL) {
20
        head = newNode;
21
        return head;
22
    }
23

24
    struct ListNode *p = head;
25
    while (p->next != NULL) {
26
        p = p->next;
27
    }
28
    p->next = newNode;
29
    return head;
30
}
31

32
void traverseList(struct ListNode *head) {
33
    struct ListNode *p = head;
34
    while (p != NULL) {
35
        printf("%d ", p->data);
36
        p = p->next;
37
    }
38
}
39

40
int main() {
41
    struct ListNode *head = NULL;
42
    head = insertOrder(head, 1);
43
    head = insertOrder(head, 2);
44
    head = insertOrder(head, 3);
45
    traverseList(head);
46
    return 0;
47
}

输出：
1
1 2 3

3.头插法（倒序插入）#

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
struct ListNode {
5
    int data;
6
    struct ListNode *next;
7
};
8

9
struct ListNode *createNode(int data) {
10
    struct ListNode *newNode = (struct ListNode *)malloc(sizeof(struct ListNode));
11
    if (newNode == NULL) { exit(1); }
12
    newNode->data = data;
13
    newNode->next = NULL;
14
    return newNode;
15
}
16

17
struct ListNode *insertReverse(struct ListNode *head, int data) {
18
    struct ListNode *newNode = createNode(data);
19
    newNode->next = head;
20
    head = newNode;
21
    return head;
22
}
23

24
void traverseList(struct ListNode *head) {
25
    struct ListNode *p = head;
26
    while (p != NULL) {
27
        printf("%d ", p->data);
28
        p = p->next;
29
    }
30
}
31

32
int main() {
33
    struct ListNode *head = NULL;
34
    head = insertReverse(head, 1);
35
    head = insertReverse(head, 2);
36
    head = insertReverse(head, 3);
37
    traverseList(head);
38
    return 0;
39
}

输出：
1
3 2 1

4.链表遍历#

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
struct ListNode {
5
    int data;
6
    struct ListNode *next;
7
};
8

9
struct ListNode *createNode(int data) {
10
    struct ListNode *newNode = (struct ListNode *)malloc(sizeof(struct ListNode));
11
    if (newNode == NULL) { exit(1); }
12
    newNode->data = data;
13
    newNode->next = NULL;
14
    return newNode;
15
}
16

17
void traverseList(struct ListNode *head) {
18
    if (head == NULL) {
19
        printf("链表为空\n");
20
        return;
21
    }
22
    struct ListNode *p = head;
23
    printf("链表节点：");
24
    while (p != NULL) {
25
        printf("%d ", p->data);
26
        p = p->next;
27
    }
28
    printf("\n");
29
}
30

31
int main() {
32
    struct ListNode *head1 = NULL;
33
    traverseList(head1);
34

35
    struct ListNode *head2 = createNode(5);
36
    head2->next = createNode(10);
37
    head2->next->next = createNode(15);
38
    traverseList(head2);
39
    return 0;
40
}

输出：

1
链表为空
2
链表节点：5 10 15

5.查找结点#

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
struct ListNode {
5
    int data;
6
    struct ListNode *next;
7
};
8

9
int findNode(struct ListNode *head, int target) {
10
    struct ListNode *p = head;
11
    while (p != NULL) {
12
        if (p->data == target) {
13
            return 1;
14
        }
15
        p = p->next;
16
    }
17
    return 0;
18
}
19

20
int main() {
21
    struct ListNode n1 = {1, NULL}, n2 = {2, NULL}, n3 = {3, NULL};
22
    n1.next = &n2;
23
    n2.next = &n3;
24

25
    int target = 2;
26
    if (findNode(&n1, target)) {
27
        printf("找到值为 %d 的节点\n", target);
28
    } else {
29
        printf("未找到值为 %d 的节点\n", target);
30
    }
31

32
    target = 4;
33
    if (findNode(&n1, target)) {
34
        printf("找到值为 %d 的节点\n", target);
35
    } else {
36
        printf("未找到值为 %d 的节点\n", target);
37
    }
38

39
    return 0;
40
}

输出：

1
找到值为 2 的节点
2
未找到值为 4 的节点

6.删除结点#

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
struct ListNode {
5
    int data;
6
    struct ListNode *next;
7
};
8

9
struct ListNode *createNode(int data) {
10
    struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode));
11
    node->data = data;
12
    node->next = NULL;
13
    return node;
14
}
15

16
struct ListNode *deleteNode(struct ListNode *head, int target) {
17
    if (head->data == target) {
18
        struct ListNode *temp = head;
19
        head = head->next;
20
        free(temp);
21
        return head;
22
    }
23

24
    struct ListNode *p = head;
25
    while (p->next != NULL && p->next->data != target) {
26
        p = p->next;
27
    }
28

29
    if (p->next != NULL) {
30
        struct ListNode *temp = p->next;
31
        p->next = temp->next;
32
        free(temp);
33
    }
34
    return head;
35
}
36

37
void printList(struct ListNode *head) {
38
    struct ListNode *p = head;
39
    while (p != NULL) {
40
        printf("%d ", p->data);
41
        p = p->next;
42
    }
43
    printf("\n");
44
}
45

46
int main() {
47
    struct ListNode *head = createNode(10);
48
    head->next = createNode(20);
49
    head->next->next = createNode(30);
50

51
    printf("删除前：");
52
    printList(head);
53

54
    head = deleteNode(head, 20);
55

56
    printf("删除后：");
57
    printList(head);
58

59
    free(head->next);
60
    free(head);
61
    return 0;
62
}

输出：

1
删除前：10 20 30
2
删除后：10 30

7.逆置单链表#

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
struct ListNode {
5
    int data;
6
    struct ListNode *next;
7
};
8

9
struct ListNode *createNode(int data) {
10
    struct ListNode *newNode = (struct ListNode *)malloc(sizeof(struct ListNode));
11
    newNode->data = data;
12
    newNode->next = NULL;
13
    return newNode;
14
}
15

16
struct ListNode *reverseList(struct ListNode *head) {
17
    struct ListNode *prev = NULL, *curr = head, *next = NULL;
18
    while (curr != NULL) {
19
        next = curr->next;
20
        curr->next = prev;
21
        prev = curr;
22
        curr = next;
23
    }
24
    return prev;
25
}
26

27
void printList(struct ListNode *head) {
28
    struct ListNode *p = head;
29
    while (p != NULL) {
30
        printf("%d -> ", p->data);
31
        p = p->next;
32
    }
33
    printf("NULL\n");
34
}
35

36
int main() {
37
    struct ListNode *head = createNode(1);
38
    head->next = createNode(2);
39
    head->next->next = createNode(3);
40

41
    printf("逆置前：");
42
    printList(head);
43

44
    head = reverseList(head);
45

46
    printf("逆置后：");
47
    printList(head);
48

49
    struct ListNode *temp;
50
    while (head != NULL) {
51
        temp = head;
52
        head = head->next;
53
        free(temp);
54
    }
55
    return 0;
56
}

输出：

1
逆置前：1 -> 2 -> 3 -> NULL
2
逆置后：3 -> 2 -> 1 -> NULL

8.单链表归并#

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
struct ListNode {
5
    int data;
6
    struct ListNode *next;
7
};
8

9
struct ListNode *createNode(int data) {
10
    struct ListNode *newNode = (struct ListNode *)malloc(sizeof(struct ListNode));
11
    newNode->data = data;
12
    newNode->next = NULL;
13
    return newNode;
14
}
15

16
struct ListNode *mergeList(struct ListNode *l1, struct ListNode *l2) {
17
    struct ListNode dummy = {0, NULL};
18
    struct ListNode *p = &dummy;
19
    while (l1 != NULL && l2 != NULL) {
20
        if (l1->data <= l2->data) {
21
            p->next = l1;
22
            l1 = l1->next;
23
        } else {
24
            p->next = l2;
25
            l2 = l2->next;
26
        }
27
        p = p->next;
28
    }
29
    p->next = (l1 != NULL) ? l1 : l2;
30
    return dummy.next;
31
}
32

33
void printList(struct ListNode *head) {
34
    struct ListNode *p = head;
35
    while (p != NULL) {
36
        printf("%d -> ", p->data);
37
        p = p->next;
38
    }
39
    printf("NULL\n");
40
}
41

42
int main() {
43

44
    struct ListNode *l1 = createNode(1);
45
    l1->next = createNode(3);
46
    l1->next->next = createNode(5);
47

48
    struct ListNode *l2 = createNode(2);
49
    l2->next = createNode(4);
50
    l2->next->next = createNode(6);
51

52
    printf("链表1：");
53
    printList(l1);
54
    printf("链表2：");
55
    printList(l2);
56

57
    struct ListNode *mergeHead = mergeList(l1, l2);
58
    printf("归并后：");
59
    printList(mergeHead);
60

61
    struct ListNode *temp;
62
    while (mergeHead != NULL) {
63
        temp = mergeHead;
64
        mergeHead = mergeHead->next;
65
        free(temp);
66
    }
67
    return 0;
68
}

输出：

1
链表1：1 -> 3 -> 5 -> NULL
2
链表2：2 -> 4 -> 6 -> NULL
3
归并后：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL

9.单链表拆分#

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
struct ListNode {
5
    int data;
6
    struct ListNode *next;
7
};
8

9
struct ListNode *createNode(int data) {
10
    struct ListNode *newNode = (struct ListNode *)malloc(sizeof(struct ListNode));
11
    newNode->data = data;
12
    newNode->next = NULL;
13
    return newNode;
14
}
15

16
void splitList(struct ListNode *head, struct ListNode **oddHead, struct ListNode **evenHead) {
17
    struct ListNode oddDummy = {0, NULL}, evenDummy = {0, NULL};
18
    struct ListNode *oddP = &oddDummy, *evenP = &evenDummy;
19
    while (head != NULL) {
20
        if (head->data % 2 == 1) {
21
            oddP->next = head;
22
            oddP = oddP->next;
23
        } else {
24
            evenP->next = head;
25
            evenP = evenP->next;
26
        }
27
        head = head->next;
28
    }
29
    oddP->next = NULL;
30
    evenP->next = NULL;
31
    *oddHead = oddDummy.next;
32
    *evenHead = evenDummy.next;
33
}
34

35
void printList(struct ListNode *head) {
36
    struct ListNode *p = head;
37
    while (p != NULL) {
38
        printf("%d -> ", p->data);
39
        p = p->next;
40
    }
41
    printf("NULL\n");
42
}
43

44
int main() {
45
    struct ListNode *head = createNode(1);
46
    head->next = createNode(2);
47
    head->next->next = createNode(3);
48
    head->next->next->next = createNode(4);
49
    head->next->next->next->next = createNode(5);
50

51
    printf("原链表：");
52
    printList(head);
53

54
    struct ListNode *oddHead, *evenHead;
55
    splitList(head, &oddHead, &evenHead);
56

57
    printf("奇数链表：");
58
    printList(oddHead);
59
    printf("偶数链表：");
60
    printList(evenHead);
61

62
    struct ListNode *temp;
63
    while (oddHead != NULL) {
64
        temp = oddHead;
65
        oddHead = oddHead->next;
66
        free(temp);
67
    }
68
    while (evenHead != NULL) {
69
        temp = evenHead;
70
        evenHead = evenHead->next;
71
        free(temp);
72
    }
73
    return 0;
74
}

输出：

1
原链表：1 -> 2 -> 3 -> 4 -> 5 -> NULL
2
奇数链表：1 -> 3 -> 5 -> NULL
3
偶数链表：2 -> 4 -> NULL

10.循环链表#

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
struct ListNode {
5
    int data;
6
    struct ListNode *next;
7
};
8

9
struct ListNode *createNode(int data) {
10
    struct ListNode *newNode = (struct ListNode *)malloc(sizeof(struct ListNode));
11
    newNode->data = data;
12
    newNode->next = NULL;
13
    return newNode;
14
}
15

16
struct ListNode *createCircularList(int arr[], int n) {
17
    if (n == 0) return NULL;
18
    struct ListNode *head = createNode(arr[0]);
19
    struct ListNode *p = head;
20
    for (int i = 1; i < n; i++) {
21
        p->next = createNode(arr[i]);
22
        p = p->next;
23
    }
24
    p->next = head;
25
    return head;
26
}
27

28
void printCircularList(struct ListNode *head) {
29
    if (head == NULL) return;
30
    struct ListNode *p = head;
31
    do {
32
        printf("%d -> ", p->data);
33
        p = p->next;
34
    } while (p != head);
35
    printf("(回到头节点%d)\n", head->data);
36
}
37

38
int main() {
39
    int arr[] = {10, 20, 30};
40
    int n = sizeof(arr) / sizeof(arr[0]);
41

42
    struct ListNode *head = createCircularList(arr, n);
43
    printf("循环链表：");
44
    printCircularList(head);
45

46
    struct ListNode *p = head->next, *temp;
47
    head->next = NULL;
48
    while (p != NULL) {
49
        temp = p;
50
        p = p->next;
51
        free(temp);
52
    }
53
    free(head);
54
    return 0;
55
}

输出：

1
循环链表：10 -> 20 -> 30 -> (回到头节点10)

11.约瑟夫环问题#

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
struct ListNode {
5
    int data;
6
    struct ListNode *next;
7
};
8

9
struct ListNode *createNode(int data) {
10
    struct ListNode *newNode = (struct ListNode *)malloc(sizeof(struct ListNode));
11
    newNode->data = data;
12
    newNode->next = NULL;
13
    return newNode;
14
}
15

16
int josephus(int n, int m) {
17
    if (n == 1) return 1;
18
    struct ListNode *head = createNode(1);
19
    struct ListNode *p = head;
20
    for (int i = 2; i <= n; i++) {
21
        p->next = createNode(i);
22
        p = p->next;
23
    }
24
    p->next = head;
25

26
    struct ListNode *prev = p;
27
    p = head;
28
    while (p->next != p) {
29
        for (int i = 1; i < m; i++) {
30
            prev = p;
31
            p = p->next;
32
        }
33
        prev->next = p->next;
34
        free(p);
35
        p = prev->next;
36
    }
37

38
    int res = p->data;
39
    free(p);
40
    return res;
41
}
42

43
int main() {
44
    int n = 5, m = 3;
45
    int last = josephus(n, m);
46
    printf("%d个人围成圈，每次数%d步淘汰，最后剩余的是第%d个人\n", n, m, last);
47
    return 0;
48
}

输出：

1
5个人围成圈，每次数3步淘汰，最后剩余的是第4个人

应用#

7-1 sdut-C语言实验-顺序建立链表
输入N个整数，按照输入的顺序建立单链表存储，并遍历所建立的单链表，输出这些数据。
输入格式：第一行输入整数的个数N；
第二行依次输入每个整数。
输出格式：输出这组整数。
输入示例：
1
8
2
12 56 4 6 55 15 33 62
输出示例：
1
12 56 4 6 55 15 33 62

7-1 解答：

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
typedef struct Node{
5
    int data;
6
    struct Node *next;
7
}Node;
8

9
int main(){
10
    int n;
11
    scanf("%d",&n);
12
    Node *head = NULL;
13
    Node *tail = NULL;
14
    Node *p = NULL;
15
    for(int i=0;i<n;i++){
16
        p=(Node *)malloc(sizeof(Node));
17
        scanf("%d",&p->data);
18
        p->next=NULL;
19
        if(head==NULL){
20
            head =p;
21
            tail=p;
22
        }else{
23
            tail->next=p;
24
            tail=p;
25
        }
26
    }
27
    p=head;
28
    while(p!=NULL){
29
        printf("%d",p->data);
30
        if(p->next!=NULL){
31
            printf(" ");
32
        }
33
        p=p->next;
34
    }
35
    return 0;
36
}

7-2 sdut-C语言实验-逆序建立链表
输入整数个数N，再输入N个整数，按照这些整数输入的相反顺序建立单链表，并依次遍历输出单链表的数据。
输入格式：第一行输入整数N;
第二行依次输入N个整数，逆序建立单链表。
输出格式：依次输出单链表所存放的数据。
输入示例：
1
10
2
11 3 5 27 9 12 43 16 84 22
输出示例：
1
22 84 16 43 12 9 27 5 3 11

7-2 解答：

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
typedef struct Node{
5
    int data;
6
    struct Node *next;
7
}Node;
8

9
int main(){
10
    int n;
11
    scanf("%d",&n);
12
    Node *head=NULL;
13
    Node *new_a=NULL;
14
    for(int i=0;i<n;i++){
15
        new_a=(Node *)malloc(sizeof(Node));
16
        scanf("%d",&new_a->data);
17
        new_a->next=head;
18
        head=new_a;
19
    }
20
    Node *p=head;
21
    while(p!=NULL){
22
        printf("%d",p->data);
23
        if(p->next!=NULL){
24
            printf(" ");
25
        }
26
        p=p->next;
27
    }
28
    return 0;
29
}

7-3 sdut-C语言实验-链表的结点插入
给出一个只有头指针的链表和 n 次操作，每次操作为在链表的第 m 个元素后面插入一个新元素x。若m 大于链表的元素总数则将x放在链表的最后。
输入格式：多组输入。每组数据首先输入一个整数n(n∈[1,100])，代表有n次操作。
接下来的n行，每行有两个整数Mi(Mi∈[0,10000])，Xi。
输出格式：对于每组数据。从前到后输出链表的所有元素,两个元素之间用空格隔开。
输入示例：
1
4
2
1 1
3
1 2
4
0 3
5
100 4
输出示例：
1
3 1 2 4

7-3 解答：

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
typedef struct Node {
5
    int data;
6
    struct Node *next;
7
} Node;
8

9
int main() {
10
    int n;
11
    while (scanf("%d", &n) != EOF) {
12
        Node *head = (Node *)malloc(sizeof(Node));
13
        head->next = NULL;
14
        for (int i = 0; i < n; i++) {
15
            int m, x;
16
            scanf("%d %d", &m, &x);
17
            Node *new_node = (Node *)malloc(sizeof(Node));
18
            new_node->data = x;
19
            new_node->next = NULL;
20
            Node *p_len = head->next;
21
            int len = 0;
22
            while (p_len != NULL) {
23
                len++;
24
                p_len = p_len->next;
25
            }
26
            Node *p_insert = head;
27
            if (m > len) {
28
                while (p_insert->next != NULL) {
29
                    p_insert = p_insert->next;
30
                }
31
                p_insert->next = new_node;
32
            } else {
33
                int count = 0;
34
                while (count < m && p_insert->next != NULL) {
35
                    p_insert = p_insert->next;
36
                    count++;
37
                }
38
                new_node->next = p_insert->next;
39
                p_insert->next = new_node;
40
            }
41
        }
42
        Node *p = head->next;
43
        int first = 1;
44
        while (p != NULL) {
45
            if (!first) {
46
                printf(" ");
47
            }
48
            printf("%d", p->data);
49
            first = 0;
50
            p = p->next;
51
        }
52
        printf("\n");
53
    }
54
    return 0;
55
}

7-4 sdut-C语言实验-单链表中重复元素的删除
按照数据输入的相反顺序（逆位序）建立一个单链表，并将单链表中重复的元素删除（值相同的元素只保留最后输入的一个）。
输入格式：第一行输入元素个数 n (1 <= n <= 15)；
第二行输入 n 个整数，保证在 int 范围内。
输出格式：第一行输出初始链表元素个数；
第二行输出按照逆位序所建立的初始链表；
第三行输出删除重复元素后的单链表元素个数；
第四行输出删除重复元素后的单链表。
输入示例：
1
10
2
21 30 14 55 32 63 11 30 55 30
输出示例：
1
10
2
30 55 30 11 63 32 55 14 30 21
3
7
4
30 55 11 63 32 14 21

7-4 解答：

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
typedef struct Node {
5
    int data;
6
    struct Node *next;
7
} Node;
8

9
int main() {
10
    int n;
11
    scanf("%d", &n);
12
    Node *head = (Node *)malloc(sizeof(Node));
13
    head->next = NULL;
14
    int num;
15
    for (int i = 0; i < n; i++) {
16
        scanf("%d", &num);
17
        Node *new_node = (Node *)malloc(sizeof(Node));
18
        new_node->data = num;
19
        new_node->next = head->next;
20
        head->next = new_node;
21
    }
22
    int init_len = 0;
23
    Node *p = head->next;
24
    while (p != NULL) {
25
        init_len++;
26
        p = p->next;
27
    }
28
    printf("%d\n", init_len);
29
    p = head->next;
30
    int first = 1;
31
    while (p != NULL) {
32
        if (!first) {
33
            printf(" ");
34
        }
35
        printf("%d", p->data);
36
        first = 0;
37
        p = p->next;
38
    }
39
    printf("\n");
40
    Node *cur = head->next;
41
    while (cur != NULL) {
42
        Node *pre = cur;
43
        Node *temp = cur->next;
44
        while (temp != NULL) {
45
            if (temp->data == cur->data) {
46
                pre->next = temp->next;
47
                free(temp);
48
                temp = pre->next;
49
            } else {
50
                pre = temp;
51
                temp = temp->next;
52
            }
53
        }
54
        cur = cur->next;
55
    }
56
    int new_len = 0;
57
    p = head->next;
58
    while (p != NULL) {
59
        new_len++;
60
        p = p->next;
61
    }
62
    printf("%d\n", new_len);
63
    p = head->next;
64
    first = 1;
65
    while (p != NULL) {
66
        if (!first) {
67
            printf(" ");
68
        }
69
        printf("%d", p->data);
70
        first = 0;
71
        p = p->next;
72
    }
73
    printf("\n");
74
    return 0;
75
}

7-5 sdut-C语言实验-链表的逆置
输入多个整数，以-1作为结束标志，顺序建立一个带头结点的单链表，之后对该单链表的数据进行逆置，并输出逆置后的单链表数据。
输入格式：输入多个整数，以-1作为结束标志。
输出格式：输出逆置后的单链表数据。
输入示例：
1
12 56 4 6 55 15 33 62 -1
输出示例：
1
62 33 15 55 6 4 56 12

7-5 解答：

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
typedef struct Node{
5
    int data;
6
    struct Node *next;
7
}Node;
8

9
int main(){
10
    Node *head = (Node *)malloc(sizeof(Node));
11
    head->next=NULL;
12
    Node *tail = head;
13
    int num;
14
    while(1){
15
        scanf("%d",&num);
16
        if(num==-1){
17
            break;
18
        }
19
        Node *newNode = (Node *)malloc(sizeof(Node));
20
        newNode->data = num;
21
        newNode->next = NULL;
22
        tail->next = newNode;
23
        tail = newNode;
24
    }
25
    if (head->next != NULL && head->next->next != NULL) {
26
        Node *pre = NULL;
27
        Node *cur = head->next;
28
        Node *next;
29
        while (cur != NULL) {
30
            next = cur->next;
31
            cur->next = pre;
32
            pre = cur;
33
            cur = next;
34
        }
35
        head->next = pre;
36
    }
37
    Node *p = head->next;
38
    int first = 1;
39
    while (p != NULL) {
40
        if (!first) {
41
            printf(" ");
42
        }
43
        printf("%d", p->data);
44
        first = 0;
45
        p = p->next;
46
    }
47
    printf("\n");
48
    return 0;
49
}

7-6 sdut-C语言实验-有序链表的归并
分别输入两个有序的整数序列（分别包含M和N个数据），建立两个有序的单链表，将这两个有序单链表合并成为一个大的有序单链表，并依次输出合并后的单链表数据。
输入格式：第一行输入M与N的值；
第二行依次输入M个有序的整数；
第三行依次输入N个有序的整数。
输出格式：输出合并后的单链表所包含的M+N个有序的整数。
输入示例：
1
6 5
2
1 23 26 45 66 99
3
14 21 28 50 100
输出示例：
1
1 14 21 23 26 28 45 50 66 99 100

7-6 解答：

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
typedef struct Node {
5
    int data;
6
    struct Node *next;
7
} Node;
8

9
int main() {
10
    int M, N;
11
    scanf("%d %d", &M, &N);
12
    Node *head1 = (Node *)malloc(sizeof(Node));
13
    head1->next = NULL;
14
    Node *tail1 = head1;
15
    int num;
16
    for (int i = 0; i < M; i++) {
17
        scanf("%d", &num);
18
        Node *newNode = (Node *)malloc(sizeof(Node));
19
        newNode->data = num;
20
        newNode->next = NULL;
21
        tail1->next = newNode;
22
        tail1 = newNode;
23
    }
24
    Node *head2 = (Node *)malloc(sizeof(Node));
25
    head2->next = NULL;
26
    Node *tail2 = head2;
27
    for (int i = 0; i < N; i++) {
28
        scanf("%d", &num);
29
        Node *newNode = (Node *)malloc(sizeof(Node));
30
        newNode->data = num;
31
        newNode->next = NULL;
32
        tail2->next = newNode;
33
        tail2 = newNode;
34
    }
35
    Node *mergeHead = (Node *)malloc(sizeof(Node));
36
    Node *mergeTail = mergeHead;
37
    Node *p = head1->next;
38
    Node *q = head2->next;
39
    while (p != NULL && q != NULL) {
40
        if (p->data <= q->data) {
41
            mergeTail->next = p;
42
            p = p->next;
43
        } else {
44
            mergeTail->next = q;
45
            q = q->next;
46
        }
47
        mergeTail = mergeTail->next;
48
    }
49
    if (p != NULL) {
50
        mergeTail->next = p;
51
    }
52
    if (q != NULL) {
53
        mergeTail->next = q;
54
    }
55
    Node *k = mergeHead->next;
56
    int first = 1;
57
    while (k != NULL) {
58
        if (!first) {
59
            printf(" ");
60
        }
61
        printf("%d", k->data);
62
        first = 0;
63
        k = k->next;
64
    }
65
    printf("\n");
66
    return 0;
67
}

7-7 sdut-C语言实验-单链表的拆分
输入N个整数顺序建立一个单链表，将该单链表拆分成两个子链表，第一个子链表存放了所有的偶数，第二个子链表存放了所有的奇数。两个子链表中数据的相对次序与原链表一致。
输入格式：第一行输入整数N;；
第二行依次输入N个整数。
输出格式：第一行分别输出偶数链表与奇数链表的元素个数；
第二行依次输出偶数子链表的所有数据；
第三行依次输出奇数子链表的所有数据。
输入示例：
1
10
2
1 3 22 8 15 999 9 44 6 1001
输出示例：
1
4 6
2
22 8 44 6
3
1 3 15 999 9 1001

7-7 解答：

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
typedef struct Node {
5
    int data;
6
    struct Node *next;
7
} Node;
8

9
int main() {
10
    int N;
11
    scanf("%d", &N);
12
    Node *head = (Node *)malloc(sizeof(Node));
13
    head->next = NULL;
14
    Node *tail = head;
15
    int num;
16
    for (int i = 0; i < N; i++) {
17
        scanf("%d", &num);
18
        Node *newNode = (Node *)malloc(sizeof(Node));
19
        newNode->data = num;
20
        newNode->next = NULL;
21
        tail->next = newNode;
22
        tail = newNode;
23
    }
24
    Node *evenHead = (Node *)malloc(sizeof(Node));
25
    Node *evenTail = evenHead;
26
    evenHead->next = NULL;
27
    Node *oddHead = (Node *)malloc(sizeof(Node));
28
    Node *oddTail = oddHead;
29
    oddHead->next = NULL;
30
    int evenCount = 0, oddCount = 0;
31
    Node *p = head->next;
32
    Node *tmp;
33
    while (p != NULL) {
34
        tmp = p->next;
35
        if (p->data % 2 == 0) {
36
            evenTail->next = p;
37
            evenTail = p;
38
            evenTail->next = NULL;
39
            evenCount++;
40
        } else {
41
            oddTail->next = p;
42
            oddTail = p;
43
            oddTail->next = NULL;
44
            oddCount++;
45
        }
46
        p = tmp;
47
    }
48
    printf("%d %d\n", evenCount, oddCount);
49
    Node *q = evenHead->next;
50
    int first = 1;
51
    while (q != NULL) {
52
        if (!first) printf(" ");
53
        printf("%d", q->data);
54
        first = 0;
55
        q = q->next;
56
    }
57
    printf("\n");
58
    q = oddHead->next;
59
    first = 1;
60
    while (q != NULL) {
61
        if (!first) printf(" ");
62
        printf("%d", q->data);
63
        first = 0;
64
        q = q->next;
65
    }
66
    printf("\n");
67
    return 0;
68
}

7-8 sdut-C语言实验-双向链表
学会了单向链表，我们又多了一种解决问题的能力，单链表利用一个指针就能在内存中找到下一个位置，这是一个不会轻易断裂的链。但单链表有一个弱点——不能回指。比如在链表中有两个节点A,B，他们的关系是B是A的后继，A指向了B，便能轻易经A找到B,但从B却不能找到A。一个简单的想法便能轻易解决这个问题——建立双向链表。在双向链表中，A有一个指针指向了节点B，同时，B又有一个指向A的指针。这样不仅能从链表头节点的位置遍历整个链表所有节点，也能从链表尾节点开始遍历所有节点。对于给定的一列数据，按照给定的顺序建立双向链表，按照关键字找到相应节点，输出此节点的前驱节点关键字及后继节点关键字。
输入格式：第一行两个正整数n（代表节点个数），m（代表要找的关键字的个数）。第二行是n个数（n个数没有重复），利用这n个数建立双向链表。接下来有m个关键字，每个占一行。
输出格式：对给定的每个关键字，输出此关键字前驱节点关键字和后继节点关键字。如果给定的关键字没有前驱或者后继，则不输出。
注意：每个给定关键字的输出占一行。一行输出的数据之间有一个空格，行首、行末无空格。
输入示例：
1
10 3
2
1 2 3 4 5 6 7 8 9 0
3
3
4
5
5
0
输出示例：
1
2 4
2
4 6
3
9

7-8 解答：

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
typedef struct DNode {
5
    int data;
6
    struct DNode *prev;
7
    struct DNode *next;
8
} DNode;
9

10
int main() {
11
    int n, m;
12
    scanf("%d %d", &n, &m);
13
    DNode *head = (DNode *)malloc(sizeof(DNode));
14
    head->prev = NULL;
15
    head->next = NULL;
16
    DNode *tail = head;
17
    int num;
18
    for (int i = 0; i < n; i++) {
19
        scanf("%d", &num);
20
        DNode *newNode = (DNode *)malloc(sizeof(DNode));
21
        newNode->data = num;
22
        newNode->prev = tail;
23
        newNode->next = NULL;
24
        tail->next = newNode;
25
        tail = newNode;
26
    }
27
    int key;
28
    for (int i = 0; i < m; i++) {
29
        scanf("%d", &key);
30
        DNode *p = head->next;
31
        while (p != NULL) {
32
            if (p->data == key) {
33
                int hasPrev = 0, hasNext = 0;
34
                int prevData, nextData;
35
                if (p->prev != head) {
36
                    hasPrev = 1;
37
                    prevData = p->prev->data;
38
                }
39
                if (p->next != NULL) {
40
                    hasNext = 1;
41
                    nextData = p->next->data;
42
                }
43
                if (hasPrev && hasNext) {
44
                    printf("%d %d\n", prevData, nextData);
45
                } else if (hasPrev) {
46
                    printf("%d\n", prevData);
47
                } else if (hasNext) {
48
                    printf("%d\n", nextData);
49
                }
50
                break;
51
            }
52
            p = p->next;
53
        }
54
    }
55
    return 0;
56
}

7-9 sdut-C语言实验-约瑟夫问题
n个人想玩残酷的死亡游戏，游戏规则如下：
n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人被杀，剩下的人继续游戏，活到最后的一个人是胜利者。
请输出最后一个人的编号。
输入格式：输入n和m值。
输出格式：输出胜利者的编号。
输入示例：
1
5 3
输出示例：
1
4

7-9 解答：

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
typedef struct Node {
5
    int num;
6
    struct Node *next;
7
} Node;
8

9
int main() {
10
    int n, m;
11
    scanf("%d %d", &n, &m);
12
    Node *head = NULL;
13
    Node *tail = NULL;
14
    for (int i = 1; i <= n; i++) {
15
        Node *newNode = (Node *)malloc(sizeof(Node));
16
        newNode->num = i;
17
        newNode->next = NULL;
18
        if (head == NULL) {
19
            head = newNode;
20
            tail = newNode;
21
        } else {
22
            tail->next = newNode;
23
            tail = newNode;
24
        }
25
    }
26
    tail->next = head;
27
    Node *p = head;
28
    Node *pre = tail;
29
    int count = 0;
30
    while (p->next != p) {
31
        count++;
32
        if (count == m) {
33
            pre->next = p->next;
34
            free(p);
35
            p = pre->next;
36
            count = 0;
37
        } else {
38
            pre = p;
39
            p = p->next;
40
        }
41
    }
42
    printf("%d\n", p->num);
43
    return 0;
44
}

7-10 sdut-C语言实验-不敢死队问题
说到“敢死队”，大家不要以为我来介绍电影了，因为数据结构里真有这么道程序设计题目，原题如下：
有M个敢死队员要炸掉敌人的一个碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。
这题本来就叫“敢死队”。“谁都不想去”，就这一句我觉得这个问题也只能叫“不敢死队问题”。今天大家就要完成这道不敢死队问题。我们假设排长是1号，按照上面介绍，从1号开始数，数到5的那名战士去执行任务，那么排长是第几个去执行任务的？
输入格式：输入包括多组数据，每组一行，包含一个整数M（0<=M<=10000)（敢死队人数），若M==0，输入结束，不做处理。
输出格式：输出一个整数n，代表排长是第n个去执行任务。
输入示例：
1
9
2
6
3
223
4
0
输出示例：
1
2
2
6
3
132

7-10 解答：

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
typedef struct Node {
5
    int num;
6
    struct Node *next;
7
} Node;
8

9
int main() {
10
    int M;
11
    while (scanf("%d", &M) && M != 0) {
12
        if (M == 0) break;
13
        if (M == 1) {
14
            printf("1\n");
15
            continue;
16
        }
17
        Node *head = NULL;
18
        Node *tail = NULL;
19
        for (int i = 1; i <= M; i++) {
20
            Node *newNode = (Node *)malloc(sizeof(Node));
21
            newNode->num = i;
22
            newNode->next = NULL;
23
            if (head == NULL) {
24
                head = newNode;
25
                tail = newNode;
26
            } else {
27
                tail->next = newNode;
28
                tail = newNode;
29
            }
30
        }
31
        tail->next = head;
32
        Node *p = head;
33
        Node *pre = tail;
34
        int count = 0;
35
        int order = 0;
36
        int result = 0;
37
        while (1) {
38
            count++;
39
            if (count == 5) {
40
                order++;
41
                if (p->num == 1) {
42
                    result = order;
43
                    pre->next = p->next;
44
                    free(p);
45
                    break;
46
                }
47
                pre->next = p->next;
48
                free(p);
49
                p = pre->next;
50
                count = 0;
51
            } else {
52
                pre = p;
53
                p = p->next;
54
            }
55
        }
56
        printf("%d\n", result);
57
    }
58
    return 0;
59
}

总结#

OK了，今天你学会了C语言程序的链表及其相关知识点！难度一定很大！已经要多看多分析，思考一下具体的运行流程，那么我们一起加油吧！

音乐

Pigeons2023

音乐

动态内存分配#

链表基础#

1. 链表节点的定义#

2. 核心语法#

链表的插入操作#

1. 倒序插入（头插法）#

2. 顺序插入（尾插法）#

链表的查找操作#

1.按值查找结点#

2.按位置查找结点#

链表的删除操作#

1.按值删除结点#

逆置单链表#

1.迭代法逆置单链表#

单链表归并#

1.归并两个升序单链表#

单链表拆分#

1.按数值奇偶拆分单链表#

循环链表#

1.创建循环链表#

约瑟夫环问题#

1.约瑟夫环求解#

示例#

1.链表节点定义+创建节点#

2.尾插法（顺序插入）#

3.头插法（倒序插入）#

4.链表遍历#

5.查找结点#

6.删除结点#

7.逆置单链表#

8.单链表归并#

9.单链表拆分#

10.循环链表#

11.约瑟夫环问题#

应用#

总结#

支持与分享

评论区

音乐

目录