编写算法,将一个头指针为head不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。_

wangcai

2024年10月16日 23:26

void Circle(LinkList *head){

if(!head) return false;

LinkList *p = head;

while(p->next){

p = p -> next;

}

p -> next = head;

}

mhhhx

2024年10月11日 15:33

void change(LNode* head){
    auto p = head;
    while(p->next){//找到链表中的最后一个结点
        p = p->next;
    }
    
    p->next = head;//将链表节点的next指针指向head
}

时间复杂度：O(n)

我与代码的故事

2024年9月29日 16:32

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。

2024年10月11日 15:32

我与代码的故事回复 mhhhx：感谢纠正

2024年10月11日 19:16

我与代码的故事回复我与代码的故事： while(p -> next)

2024年10月11日 19:17

lsssssj

2024年9月19日 20:41

void func(Node *L){ Node* head = L; while(L->next !=NULL){ L=L->next; } L-next = head; return; }

Conan_G

2024年9月12日 14:57

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）。

2893385654

2024年9月6日 21:16

#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) {

link *temp=head;

while(temp) {

printf("%d",temp->data);

if(temp->next!=NULL)

printf("->");

temp=temp->next;

}

//冒泡排序

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;

}

temp=temp->next;

qemp=qemp->next;

}

return head;

}

//生成单循环链表

link *creatxunhuan(link *head) {

link *temp=head;

while(temp->next!=NULL)

temp=temp->next;

temp->next=head;

return head;

}

void display1(link *head){

link *temp=head;

while(temp->next!=head) {

printf("%d",temp->data);

if(temp->next!=head)

printf("->");

temp=temp->next;

}

printf("%d",temp->data);

}

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;

}

步步高

2024年9月3日 19:52

void linklist_c(Lnode* head) {
   Lnode* p;
   p = head;
   if (!p)
       return ERROE;
   while (p->next != NULL)
       p = p->next;
   p->next = head;
}

adgdsfa

2024年9月3日 15:30

void tran(Node *L){

Node* head = L;

while(L->next !=NULL){

L=L->next;

}

L-next = head;

return;

}

折翼的小鸟先生

2024年8月29日 14:54

void linklist_c(LinkList L){
   Lnode *p=L;
   while(p->next!=NULL){
       p=p-next;
   }
   p-next=L;
}

嘤狐

2024年8月29日 13:47

if(head==NULL)return;

Node *p=head;

while(p->next!=NULL)p=p->next;

p->next=head;

时间复杂度：O(n)

现在只想上岸

2024年8月27日 11:37

cvb

Mapleman

2024年8月15日 09:02

void linklist_c(Lnode* head) {
   Lnode* p;
   p = head;
   if (!p)
       return ERROE;
   while (p->next != NULL)
       p = p->next;
   p->next = head;
}

缘小遇

2024年8月14日 15:03

typedef struct LNode{

int data;

struct LNode *next;

}LNode,*LinkList;

LinkList Transform(LinkList &head){

if(head==NULL)

return head;

LNode *p=head;

while(p->next!=NULL)

p=p->next;

p->next=head;

return head;

}//复杂度O(n)

与或非

2024年7月26日 17:39

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;
}

Austin00

2024年7月26日 12:17

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;
	
}

takanasi

2024年5月29日 18:02

void change(LNode *head){

LNode *tmp = head;

while(tmp->next != null){

tmp = tmp->next;

}

tmp->next = head;

}

公交车呢

2024年3月12日 21:34

void linklist_c(Lnode *head){

Lnode *p; p=head;

if(!p) return ERROR;

while(p->next!=NULL)

p=p->next;

p->next=head;

}

公交车呢

2024年3月12日 21:32

O(n)

fzh

2023年11月30日 20:34

时间复杂度o(n)

void Change(LinkNode * head)

{LinkNode* p=head;

while(p!=NULL) p=p->next;

p->next-head;

return;

}

gaoshipeng

2023年11月24日 09:58

node* ChangeToCycleLink(node* head)

{

node* h;

h=head;

while(h->next!=NULL)

{

h=h->next;

}

h->next=head;

return head;

}

woaixinzhou

2023年11月20日 08:29

void fun(LinkList *head)

{

LinkList *p = head;

while(p->next != NULL) p = p->next; //找到最后一个结点

p->next = head; //改为循环链表

return;

}

/*

对于表长为n的链表，其时间复杂度为O(n)，基本操作是找最后一个结点的p = p->next;指针移动语句

*/

山药男孩

2023年11月3日 19:01

void LinkList(Lnode *head){

Lnode *p;

p=head;

if(!p) return error;

while(p->next!=null){

p=p->next;

}

p->next=head;

}

o(n)

WhiteWing

2023年11月2日 14:09

void Change(LinkList &head)

{

LinkNode *p = head;

while(p->next!=NULL)

{

p=p->next;

}

p->next = head;

}

绘州景

2023年10月22日 18:38

评论区中的有些答案和参考答案有一点差别，差别在于传参部分，有同学使用了&head，而参考答案使用的是*head，考虑到题目要求并不需要修改head指针，我认为更好的方式应该是参考答案中的*head。

adidam9633

2023年9月23日 20:08

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）。

yunke

2023年9月14日 22:10

思路

遍历单链表直到尾结点，将尾结点指针指向头指针head指向结点

时间主要开销在遍历部分

时间n+1，O(n)

lightstar

2023年9月6日 22:06

不知

高康

2023年7月24日 21:47

int CulList(List &head)

{

List p=head;

if(!p) return error;

whlie(p->next)

{

p=p->next;
}

p->next=head;

return trun;

}

Syou

2023年7月21日 21:39

void linklist_c(Lnode *head){

Lnode *p; p=head;

if(!p) return ERROR;

while(p->next!=NULL)

p=p->next;

p->next=head;

}

O(N)

Friday

2023年7月11日 16:04

void circulate(LinkList L, *head){
LNode *p;

p=head->next;

if(p==NULL) return;

while(p){

p=p->next;

}

p->next=head;

}

时间复杂度为O（n）

hunhun

2023年6月29日 10:29

if(head==NULL){

return ERROR

}

LNode *tail=head->next

while(tail!=NULL){

tail=tail->next;

}

tail->next=head

return True

小汪_brit

2022年10月25日 11:12

void exchange(linklist &head)

{

linklist p=head;

while(p->next) p = p->next;

p->next = head;

}

实际按复杂度为 O(n)

冲冲冲123···

2022年2月15日 15:57

#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;
}

hulin

2021年9月10日 21:53

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=p->next;

}

p->next = L->next; // 令尾结点的next指向第一个结点

return true;

}

该算法的主体在于寻找单链表的尾结点，算法的时间复杂度T(n)=O(n)，n为单链表的长度

hulin 回复 hulin：第五行：p == L；第九行：p->next = L； // 令尾结点的next指向第一个结点

2021年9月10日 21:57

hulin

2021年9月10日 21:53

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=p->next;

}

p->next = L->next; // 令尾结点的next指向第一个结点

return true;

}

该算法的主体在于寻找单链表的尾结点，算法的时间复杂度T(n)=O(n)，n为单链表的长度

a575301453

2020年6月7日 17:19

void CreateCircle(ListNode* head)

{

ListNode *p=head;

if(!p) return;

while(p->next!=NULL)

p=p->next;

p->next=head;

}

[数据结构 P1076] 编写算法,将一个头指针为head不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。

登录后提交答案