问题描述

用循环链表实现：N个乘客同乘一艘船，因为严重超载，加上风高浪大，危险万分，因此船长告诉乘客，只有将部分乘客投入海中，其余人才能幸免于难。 无奈，大家只得同意这种办法。于是N个人围成一圈(从1，2，3…N分别编号)。由编号为1的人开始，依次报数，数到第M人，便把他投入大海中， 然后再从他的下一个人数起，数到第M人，再将他扔到大海中，如此循环地进行，直到剩下K个乘客为止。按顺序依次输出被扔下大海的乘客的编号。

提交格式： 实现int * solve(int N,int M,int K)函数。 函数参数为乘客人数N、间隔人数M和剩余乘客人数K，1<=N<=1000，1<=M<=500000，0<=K<N。 函数返回值为按顺序被扔下大海乘客编号的数组。 请不要printf输出任何内容。

核心思路

  1. 创建并初始化循环链表；

  2. 按照间隔人数M删除节点，同时记录被扔下大海乘客编号；

  3. 返回按顺序被扔下大海乘客编号的数组地址。

实现要点

  1. 头节点不存储编号，循环时注意绕开；

  2. 动态内存分配后，应立即判断是否分配成功；

  3. 删除i==M处节点时，需从i==M-1处节点对下一个节点进行判断，从而绕开头节点。这使得当M==1时，需从i==0处节点进行判断,不在i的循环范围1~M之中。故M==1的情况须单独处理。

测试样例

输入样例1： 9 3 2 输出样例1： 3 6 9 4 8 5 2

输入样例2： 12 5 6 输出样例2： 5 10 3 9 4 12

输入样例3： 7 1 3 输出样例3： 5 6 7

源代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
    int d;
    struct node* next;
} node;
int* solve(int N, int M, int K);
void print(int* a,int n,int k);
int main()
{
    int n, k, m;
    int* data;
    printf("请输入人数n，间隔人数m,剩余人数k:\n");
    scanf_s("%d%d%d", &n, &m, &k);
    data = solve(n, m, k);
    print(data,n,k);
    return 0;
}
int* solve(int N, int M, int K)
{
    node* Header = (node*)malloc(sizeof(node));
    if (!Header)return NULL;
    node* p, *q;
    Header->next = Header;
    p = Header;
    for (int i = 1; i <= N; ++i)
    {
        q = (node*)malloc(sizeof(node));
        if (!q)
        {
            return NULL;
        }
        q->d = i;
        q->next = p->next;
        p->next = q;
        p = q;
    }
    p = Header->next;
    int z = N - K;
    int* a = (int*)malloc(z*sizeof(int));
    if (!a)
    {
        return NULL;
    }
    int i = 1, j = N,s=0;//i控制每M个人删除;j存储剩余人数 
    if (M == 1)
    {
        for (i = 0; i < z; i++)
        {
            a[s++] = i + 1;
        }
    }
    else 
    {
        while (j > K)
        {
            if (i == M - 1)
            {
                if (p->next != Header)//不是删除第一个结点 
                {
                    q = p->next;
                    p->next = q->next;
                    a[s++] = q->d;
                }
                else//删除第一个结点 
                {
                    q = Header->next;
                    Header->next = q->next;
                    a[s++] = q->d;
                }
                free(q);
                if (p->next != Header)
                {
                    p = p->next;
                }
                else
                {
                    p = Header->next;
                }
                --j;
                i = 1;
            }
            else
            {
                if (p->next == Header)
                {
                    p = Header->next;
                }
                else
                {
                    p = p->next;
                }
                ++i;
            }
        }
    }
    return a;
}
void print(int* a,int n,int k)
{
    for (int i = 0; i < (n-k); i++)
    {
        printf("%d  ",a[i]);
    }
}