1、实现单链表逆置
无头结点:
1#include<stdio.h>
2#include<stdlib.h>
3
4typedefstructnode{
5intdata;
6structnode*next;
7}Node;
8
9//创建链表
10Node*CreateList(void){
11intval,i,n;
12Node*head,*p,*q;
13
14head=NULL;
15printf("请输入您要建立的链表长度:\n");
16scanf("%d",&n);
17printf("请输入您要输入的数据:\n");
18for(i=0;i<n;i++){
19scanf("%d",&val);
20p=(Node*)malloc(sizeof(Node));
21p->data=val;
22if(head==NULL)
23head=q=p;
24else
25q->next=p;
26q=p;
27}
28p->next=NULL;
29returnhead;
30}
31
32//链表的逆置
33Node*ReverseList(Node*head){
34Node*p,*q,*r;
35p=head;
36q=r=NULL;
37while(p){
38q=p->next;
39p->next=r;
40r=p;
41p=q;
42}
43returnr;
44}
45
46//输出链表
47voidShowList(Node*head){
48Node*p;
49p=head;
50while(p){
51printf("%d",p->data);
52p=p->next;
53}
54printf("\n");
55}
56
57voidmain(){
58Node*head;
59
60head=CreateList();
61printf("链表逆置前的数据:\n");
62ShowList(head);
63
64head=ReverseList(head);
65printf("链表逆置后的数据:\n");
66ShowList(head);
67}
2、判断单链表是否有环
判断链表是否存在环的办法为:
设置两个指针(fast,slow),初始值都指向头指针,slow每次前进一步,fast每次前进两步,如果链表存在环,则fast必定先进入环,而slow后进入环,两个指针必定相遇。(当然,fast先行从头到尾部为NULL,则为无环链表)程序如下:
1#include<stdio.h>
2#include<stdlib.h>
3
4typedefstructnode{
5intelem;
6structnode*next;
7}Node,*NodeList;
8
9boolIsExitsLoop(NodeListhead){
10NodeListslow=head,fast=head;
11while(fast&&fast->next){
12slow=slow->next;
13fast=fast->next->next;
14if(slow==fast)
15break;
16}
17return!(fast==NULL||fast->next==NULL);
18}
19
20voidmain(){
21//创建一个有环的单链表
22NodeListhead=NULL,p,q;
23for(inti=1;i<=5;i++){
24p=(NodeList)malloc(sizeof(Node));
25p->elem=i;
26if(head==NULL)
27head=q=p;
28else
29q->next=p;
30q=p;
31}
32p=(NodeList)malloc(sizeof(Node));
33p->elem=6;
34q->next=p;
35q=p;
36q->next=head->next->next->next;
37//判断单链表是否存在环
38printf("单链表是否存在环:");
39boolb=IsExitsLoop(head);
40printf("%s\n",b==false?"false":"true");
41}
3、如果单链表有环,则找到环的入口点
当fast若与slow相遇时,slow肯定没有遍历完链表,而fast已经在环内循环了n圈(1<=n),假设slow走了s步,而fast走了2s步(fast步数还等于s加上在环上多转的n圈),设环长为r,则:
2s=s+n*r;
s=n*r;
设整个链表长为L,入口环与相遇点距离为x,起点到环入口点的距离为a。
a+x=n*r;
a+x=(n-1)*r+r=(n-1)*r+L-a;
a=(n-1)r+(L–a–x);
(L–a–x)为相遇点到环入口点的距离,由此可知,从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点,于是我们从链表头、与相遇点分别设一个指针,每次各走一步,两个指针必定相遇,且相遇第一点为环入口点。程序描述如下:
1#include<stdio.h>
2#include<stdlib.h>
3
4typedefstructnode{
5intelem;
6structnode*next;
7}Node,*NodeList;
8
9//寻找环的入口点
10NodeListFindLoopPort(NodeListhead){
11NodeListslow=head,fast=head;
12while(fast&&fast->next){
13slow=slow->next;
14fast=fast->next->next;
15if(slow==fast)
16break;
17}
18if(fast==NULL||fast->next==NULL)
19returnNULL;
20slow=head;
21while(slow!=fast){
22slow=slow->next;
23fast=fast->next;
24}
25returnslow;
26}
27
28voidmain(){
29//创建一个有环的单链表
30NodeListhead=NULL,p,q;
31for(inti=1;i<=5;i++){
32p=(NodeList)malloc(sizeof(Node));
33p->elem=i;
34if(head==NULL)
35head=q=p;
36else
37q->next=p;
38q=p;
39}
40p=(NodeList)malloc(sizeof(Node));
41p->elem=6;
42q->next=p;
43q=p;
44q->next=head->next->next->next;
45//寻找环的入口点
46NodeListlist=FindLoopPort(head);
47printf("环的入口节点元素值为:%d\n",list->elem);
48}
4、判断两个单链表是否相交,如果相交,给出相交的第一个点(两个链表都不存在环)
比较好的方法有两个:
一、将其中一个链表首尾相连,检测另外一个链表是否存在环,如果存在,则两个链表相交,而检测出来的依赖环入口即为相交的第一个点。
二、如果两个链表相交,那么两个链表从相交点到链表结束都是相同的节点,我们可以先遍历一个链表,直到尾部,再遍历另外一个链表,如果也可以走到同样的结尾点,则两个链表相交。这时我们记下两个链表length,再遍历一次,长链表节点先出发前进(lengthMax-lengthMin)步,之后两个链表同时前进,每次一步,相遇的第一点即为两个链表相交的第一个点。
分享到:
相关推荐
C语言笔试面试常考题总结。 C语言笔试面试常考题总结。 C语言笔试面试常考题总结。 C语言笔试面试常考题总结。
大一初学C语言时的期末作业,涉及到链表的建立和功能的实现,涉及指针、函数、动态结构建立等方面的知识,初学者可以参考参考尝试尝试哟!!!
C语言链表类面试题.docx struct node { int data; struct node* next; }; 创建单链表的程序为: struct node* create(unsigned int n) { //创建长度为n的单链表 assert(n > 0); node* head; head = new ...
C语言链表C语言链表C语言链表C语言链表
C语言链表相关的面试题在软件开发领域的面试中是非常常见的,这是因为链表作为一种基本的数据结构,对于理解数据结构、算法以及内存管理等方面有着重要的作用。以下是一些关于C语言链表的面试题及其详细解释。 1. ...
C语言链表C语言链表C语言链表C语言链表C语言链表
C语言链表类题目 写函数建立一个有三名学生数据的单项动态链表,很全面,各种测试都试过了,环境VC6.0
小型通讯录程序c语言链表实现(源代码) CentOS下vim编辑器gcc编译器
c语言链表,用来编写c语言程序的。详细情况下了就知道了。
c语言中链表的学习,总结相当到位,对于初学者有很大的帮助!
数据结构C语言链表的实现
本资源为C语言链表PPT课件,共46页,涵盖了单链表的定义、基本操作、遍历、插入、删除、排序、逆置、约瑟夫问题等知识点。 单链表的定义 单链表是一种线性结构,每个节点由数据字段和指针字段组成。数据字段表示...
C语言——链表技术实现的学生信息管理。直接把txt文档中的代码复制到vc++ 6.0中即可。
C语言链表的应用,包括建立链表、删除链表、插入/删除元素操作
C语言链表
C语言中关于链表的总结内容,内附代码例题,详细的有条理的讲解链表内容
这是利用c语言中的链表来解决的问题,有利于你对C语言链表的更好的了解
C语言链表程序C语言链表程序
C语言链表详解PPT课件.pptx
适用于初学者学习C语言链表操作的源代码,内含链表的增添,查找,删除等基本操作,并附有详细的代码注释