编写算法,将一个头指针为head不带头结点的单链表改造为一个单向循环链表,并分析算法的时间复杂度。
void linklist_c(Lnode *head)
{Lnode *p; p=head;
if(!p) return ERROR;
while(p->next!=NULL)
p=p->next;
p->next=head;
}
// 定义单链表节点结构体 typedef struct ListNode { int data; struct ListNode *next; } ListNode;
// 将单链表改造为单向循环链表的函数 ListNode* makeCircular(ListNode* head) { if (head == NULL) { return NULL; }
ListNode* p = head; // 遍历到链表的最后一个节点 while (p->next!= NULL) { p = p->next; }
// 将最后一个节点的next指针指向头节点,形成循环链表 p->next = head;
return head; } 假设单链表的长度为n,在最坏情况下,需要遍历n个节点才能找到最后一个节点。因此,该算法的时间复 杂度为O(n)。
void cicLink(LNode *head){
LNode *rear = head;
while(rear->next != NULL){
rear = rear->next;
rear->next = head;
该算法花费时间主要在寻找单链表的表尾上,所以算法时间复杂度为O(n)。
void Circle(LinkList *head){
if(!head) return false;
LinkList *p = head;
while(p->next){
p = p -> next;
p -> next = head;
void change(LNode* head){ auto p = head; while(p->next){//找到链表中的最后一个结点 p = p->next; } p->next = head;//将链表节点的next指针指向head }
时间复杂度:O(n)
void change_cList(Lnode *head) { Lnode *p = head; //不带头 带头的话*p = head -> next //找尾结点 while(p) p = p -> next; p -> next = head; }
时间复杂度来自确定尾结点的时间为O(n)
mhhhx 回复 我与代码的故事: p最后应该指向链表的最后一个接点,你的这个最后p为NULL。
我与代码的故事 回复 mhhhx: 感谢纠正
我与代码的故事 回复 我与代码的故事: while(p -> next)
void func(Node *L){ Node* head = L; while(L->next !=NULL){ L=L->next; } L-next = head; return; }
设单链表的长度(数据结点数)为N,则该算法的时间主要花费在查找链表最后一个结点上(算法中的while循环),所以该算法的时间复杂度为O(N)。
#include<stdio.h>
#include<stdlib.h>
//设一个带头结点的单向链表的头指针为head,设计算法
//将链表的记录,按照data域的值递增排序。
typedef struct Link {
int data;
struct Link *next;
} link;
link *creatlinklist(int a[],int size) {
link *head=(link*)malloc(sizeof(link));
head->data=a[0];
head->next=NULL;
link *temp=head;
for(int i=1; i<size; i++) {
link *p=(link*)malloc(sizeof(link));
p->data=a[i];
p->next=NULL;
temp->next=p;
temp=temp->next;
return head;
void display(link *head) {
while(temp) {
printf("%d",temp->data);
if(temp->next!=NULL)
printf("->");
//冒泡排序
link *paixu(link *head,int size) {
int n;
for(int i=0; i<size-1; i++) {
link *temp=head,*qemp=head->next;
for(int j=0; j<size-i-1; j++) {
if(temp->data>qemp->data) {
n=temp->data;
temp->data=qemp->data;
qemp->data=n;
qemp=qemp->next;
//生成单循环链表
link *creatxunhuan(link *head) {
while(temp->next!=NULL)
temp->next=head;
void display1(link *head){
while(temp->next!=head) {
if(temp->next!=head)
int main()
{
int a[]= {5,2,9,3,7,1,8,6};
int size=sizeof(a)/sizeof(a[0]);
link *head=creatlinklist(a,size);
display(head);
//head=paixu(head,size);
printf("\n");
head=creatxunhuan(head);
display1(head);
return 0;
void linklist_c(Lnode* head) { Lnode* p; p = head; if (!p) return ERROE; while (p->next != NULL) p = p->next; p->next = head; }
void tran(Node *L){
Node* head = L;
while(L->next !=NULL){
L=L->next;
L-next = head;
return;
void linklist_c(LinkList L){ Lnode *p=L; while(p->next!=NULL){ p=p-next; } p-next=L; }
if(head==NULL)return;
Node *p=head;
while(p->next!=NULL)p=p->next;
cvb
typedef struct LNode{
struct LNode *next;
}LNode,*LinkList;
LinkList Transform(LinkList &head){
if(head==NULL)
LNode *p=head;
}//复杂度O(n)
typedef struct LinkNode{ int data; struct LinkNode *next; }LinkNode,*LinkList; void changeForm(LinkList &head){ LinkNode * p = head; if(!p) return; while(p != NULL) p = p->next; p->next = head; }
struct Lnode{ int data; Lnode * next; }; // 复杂度O(n) void to_rlink(Lnode *head){ Lnode * p= head ; while(p->next){ p=p->next; } p->next = head; }
void change(LNode *head){
LNode *tmp = head;
while(tmp->next != null){
tmp = tmp->next;
tmp->next = head;
void linklist_c(Lnode *head){
Lnode *p; p=head;
O(n)
时间复杂度o(n)
void Change(LinkNode * head)
{LinkNode* p=head;
while(p!=NULL) p=p->next;
p->next-head;
node* ChangeToCycleLink(node* head)
node* h;
h=head;
while(h->next!=NULL)
h=h->next;
h->next=head;
void fun(LinkList *head)
while(p->next != NULL) p = p->next; //找到最后一个结点
p->next = head; //改为循环链表
/*
对于表长为n的链表,其时间复杂度为O(n),基本操作是找最后一个结点的p = p->next;指针移动语句
*/
void LinkList(Lnode *head){
Lnode *p;
p=head;
if(!p) return error;
while(p->next!=null){
o(n)
void Change(LinkList &head)
LinkNode *p = head;
p->next = head;
评论区中的有些答案和参考答案有一点差别,差别在于传参部分,有同学使用了&head,而参考答案使用的是*head,考虑到题目要求并不需要修改head指针,我认为更好的方式应该是参考答案中的*head。
void linklist_c(Lnode *head) {Lnode *p; p=head; if(!p) return ERROR; while(p->next!=NULL) p=p->next; p->next=head; } 设单链表的长度(数据结点数)为N,则该算法的时间主要花费在查找链表最后一个结点上(算法中的while循环),所以该算法的时间复杂度为O(N)。
思路
遍历单链表直到尾结点,将尾结点指针指向头指针head指向结点
时间主要开销在遍历部分
时间n+1,O(n)
不知
int CulList(List &head)
List p=head;
whlie(p->next)
p=p->next; }
return trun;
O(N)
void circulate(LinkList L, *head){ LNode *p;
p=head->next;
if(p==NULL) return;
while(p){
时间复杂度为O(n)
if(head==NULL){
return ERROR
LNode *tail=head->next
while(tail!=NULL){
tail=tail->next;
tail->next=head
return True
void exchange(linklist &head)
linklist p=head;
while(p->next) p = p->next;
实际按复杂度为 O(n)
#include<stdio.h> #include<stdlib.h> #define M (List)malloc(sizeof(Node)) typedef struct Node{ int data; Node* next; }Node,*List;
List create(int n){ List head=NULL,tail=NULL; for(int i=0;i<n+10;i++){ List p=M; p->data=i; if(head==NULL) head=tail=p; else{ tail->next=p; tail=p; } } tail->next=NULL; return head; } void print(List head){ while(head){ printf("%d ",head->data); head=head->next; } printf("\n"); } //转变为循环链表 时间复杂度为O(n) void transform(List head){ List p=head; while(p->next) p=p->next; p->next=head; } int main(){ List head=create(0); transform(head); print(head); return 0; }
bool CircleLinkList(LinkList L){
LNode *p = (LNode *)malloc(sizeof(LNode));
if (L->next == NULL || p == NULL) // 若L为空表或内存不足分配失败则返回false
return false;
p == L->next;
while(p->next!=NULL){ // 找尾结点
p->next = L->next; // 令尾结点的next指向第一个结点
return true;
该算法的主体在于寻找单链表的尾结点,算法的时间复杂度T(n)=O(n),n为单链表的长度
hulin 回复 hulin: 第五行:p == L; 第九行:p->next = L; // 令尾结点的next指向第一个结点
void CreateCircle(ListNode* head)
ListNode *p=head;
if(!p) return;
答案:
void linkl...
用户登录可进行刷题及查看答案
登录后提交答案