请使用c语言创建单链表,实现以下功能并标注注释 0、将单链表逆置,要求不改变结点地址(建表2,倒置2) 1、找单链表中点 2、找单链表倒数第K个点 3、删除单链表倒数第K个点 4、判断单链表是否有环,如有,找出交点 5、判断两个单链表是否相交,如果相交,找出交点
时间: 2024-06-01 09:09:30 浏览: 14
#include <stdio.h>
#include <stdlib.h>
//定义链表结构体
struct Node
{
int data;
struct Node *next;
};
//创建链表函数
struct Node *createList(int n)
{
struct Node *head, *p, *q;
int i, num;
head = (struct Node *)malloc(sizeof(struct Node));
head->next = NULL;
q = head;
for (i = 0; i < n; i++)
{
printf("请输入第%d个节点的值:", i + 1);
scanf("%d", &num);
p = (struct Node *)malloc(sizeof(struct Node));
p->data = num;
p->next = NULL;
q->next = p;
q = p;
}
return head;
}
//输出链表函数
void printList(struct Node *head)
{
struct Node *p;
p = head->next;
while (p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
//逆置链表函数
void reverseList(struct Node *head)
{
struct Node *p, *q, *r;
p = head->next;
q = NULL;
while (p != NULL)
{
r = p->next;
p->next = q;
q = p;
p = r;
}
head->next = q;
}
//找中间节点函数
struct Node *findMiddleNode(struct Node *head)
{
struct Node *p, *q;
p = head->next;
q = head->next;
while (q != NULL && q->next != NULL)
{
p = p->next;
q = q->next->next;
}
return p;
}
//找倒数第k个节点函数
struct Node *findKthNode(struct Node *head, int k)
{
struct Node *p, *q;
p = head->next;
q = head->next;
while (k > 0 && q != NULL)
{
q = q->next;
k--;
}
if (k > 0)
return NULL;
while (q != NULL)
{
p = p->next;
q = q->next;
}
return p;
}
//删除倒数第k个节点函数
void deleteKthNode(struct Node *head, int k)
{
struct Node *p, *q;
p = head;
q = head->next;
while (k > 0 && q != NULL)
{
p = q;
q = q->next;
k--;
}
if (k > 0)
return;
p->next = q->next;
free(q);
}
//判断链表是否有环函数
int hasCycle(struct Node *head)
{
struct Node *p, *q;
p = head;
q = head;
while (q != NULL && q->next != NULL)
{
p = p->next;
q = q->next->next;
if (p == q)
return 1;
}
return 0;
}
//找出环的交点函数
struct Node *findCycleNode(struct Node *head)
{
struct Node *p, *q;
int flag = 0;
p = head;
q = head;
while (q != NULL && q->next != NULL)
{
p = p->next;
q = q->next->next;
if (p == q)
{
flag = 1;
break;
}
}
if (flag == 0)
return NULL;
p = head;
while (p != q)
{
p = p->next;
q = q->next;
}
return p;
}
//判断两个单链表是否相交函数
int isIntersect(struct Node *head1, struct Node *head2)
{
struct Node *p, *q;
p = head1;
q = head2;
while (p->next != NULL)
{
p = p->next;
}
while (q->next != NULL)
{
q = q->next;
}
if (p == q)
return 1;
else
return 0;
}
int main()
{
struct Node *head1, *head2, *p;
int n, k;
printf("请输入链表1的节点个数:");
scanf("%d", &n);
head1 = createList(n);
printf("链表1为:");
printList(head1);
reverseList(head1);
printf("逆置后的链表1为:");
printList(head1);
p = findMiddleNode(head1);
printf("链表1的中间节点为:%d\n", p->data);
printf("请输入链表1的倒数第k个节点:");
scanf("%d", &k);
p = findKthNode(head1, k);
printf("链表1的倒数第%d个节点为:%d\n", k, p->data);
deleteKthNode(head1, k);
printf("删除倒数第%d个节点后的链表1为:", k);
printList(head1);
if (hasCycle(head1))
{
p = findCycleNode(head1);
printf("链表1有环,环的交点为:%d\n", p->data);
}
else
{
printf("链表1没有环\n");
}
printf("请输入链表2的节点个数:");
scanf("%d", &n);
head2 = createList(n);
printf("链表2为:");
printList(head2);
if (isIntersect(head1, head2))
{
printf("链表1和链表2相交\n");
p = findCycleNode(head1);
printf("链表1和链表2的交点为:%d\n", p->data);
}
else
{
printf("链表1和链表2不相交\n");
}
return 0;
}