链表类问题
标签: 机试攻略 - 高分篇
学习人数: 22.0k


高清播放
赞赏支持

链表类问题属于选读章节,对于使用OJ测评的院校的同学来说,这类问题可以用数组来实现,没有必要用链表去实现,写起来慢不说,还容易出错,所以我们一般都直接用数组来实现,反正最后OJ能AC就行,建议这类同学跳过本节或仅做了解即可。但是对于非OJ测评的院校来说,链表类问题可以说是必考的题型。

 

一般来说有以下三种常见考点

1、猴子报数
解析:循环链表建立之后,按照题意删除节点。
2、两个有序链表合并为一个
解析:这个和两个有序数组合并为一个有序数组原理一样。
3、链表排序
解析:使用冒泡排序进行链表排序,因为冒泡排序是相邻两个元素进行比较交换,适合链表。

 

猴子报数
题目描述:
n个猴子围坐一圈并按照顺时针方向从1到n编号,从第s个猴子开始进行1到m的报数,报数到第m的猴子退出报数,从紧挨它的下一个猴子重新开始1到m的报数,如此进行下去知道所有的猴子都退出为止。求给出这n个猴子的退出的顺序表。
输入描述:
有做组测试数据.每一组数据有两行,第一行输入n(表示猴子的总数最多为100)第二行输入数据s(从第s个猴子开始报数)和数据m(第m个猴子退出报数).当输入0 0 0时表示程序结束.
输出描述:
每组数据的输出结果为一行,中间用逗号间隔。
输入样例#:
10
2 5 
5
2 3 
0
0 0
输出样例#:
6,1,7,3,10,9,2,5,8,4
4,2,1,3,5
题目来源:
DreamJudge 1081

题目解析:我们需要创建一个首尾相连的循环链表,然后先走s步,再开始循环遍历链表,每走m步删除一个节点,知道链表中只能下一个节点时结束循环。只能一个节点的判断条件是,它的下一个指针指向的是它,说明它自循环了。

 

参考代码

#include <stdio.h>  
#include <malloc.h>  
  
struct node {  
    int num;  
    struct node *next;  
};  
int n, s, m;  
//创建循环链表  
struct node* create() {  
    struct node *head, *now, *pre;  
    for (int i = 1; i <= n; i++) {  
        now = (struct node *)malloc(sizeof(node));  
        if (i == 1) {  
            head = now;  
            pre = now;  
        }  
        now->num = i;  
        now->next = head;  
        pre->next = now;  
        pre = now;  
    }  
    return head;  
};  
//按照题目要求输出  
void print(struct node *head) {  
    struct node *p, *pre;//pre是前一个节点  
    p = head;  
    s -= 1;//因为起点在第一个 所以要少走一...
登录查看完整内容


课后作业

练习题目

DreamJudge 1015 单链表
DreamJudge 1018 击鼓传花
DreamJudge 1025 合并链表
DreamJudge 1405 遍历链表


登录后开始许愿

暂无评论,来抢沙发