链表翻转初稿

wp231957 · 发表于 2022-5-8 12:09:40

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

#include <stdio.h>
#include <malloc.h>
struct Node
{
int data;
struct Node *next;
};
int main()
{
struct Node * node1;
struct Node * node2;
struct Node * node3;
struct Node * node4;
struct Node * node5;
struct Node * pmove;
node1=(struct Node*)malloc(sizeof(struct Node*));
node2=(struct Node*)malloc(sizeof(struct Node*));
node3=(struct Node*)malloc(sizeof(struct Node*));
node4=(struct Node*)malloc(sizeof(struct Node*));
node5=(struct Node*)malloc(sizeof(struct Node*));
node1->data=1;
node1->next=node2;
node2->data=2;
node2->next=node3;
node3->data=3;
node3->next=node4;
node4->data=4;
node4->next=node5;
node5->data=5;
node5->next=NULL;
//输出原始链表
pmove=node1;
while (pmove)
{
printf("%4d ",pmove->data);
pmove=pmove->next;
}
printf("\n");
//为了翻转链表，我们需要四个指针
struct Node * cur;
struct Node * next;
struct Node * pre; //还有一个是入口指针，前面有的
//1节点
pre=cur=node1;
next=cur->next;
cur->next=0;
//2节点
cur=next;
next=cur->next;
cur->next=pre;
pre=cur;
//3节点
cur=next;
next=cur->next;
cur->next=pre;
pre=cur;
//4节点
cur=next;
next=cur->next;
cur->next=pre;
pre=cur;
//5节点
cur=next;
next=cur->next;
cur->next=pre;
pre=cur;
//输出翻转后链表
pmove=cur;
while (pmove)
{
printf("%4d ",pmove->data);
pmove=pmove->next;
}
printf("\n");
return 0;
}
/*
附效果图:
PS D:\001> ./w1
1 2 3 4 5
5 4 3 2 1
*/

复制代码

wp231957 · 发表于 2022-5-8 13:05:12

第二稿：

#include <stdio.h>
#include <malloc.h>
struct Node
{
int data;
struct Node *next;
};
int main()
{
struct Node * node1;
struct Node * head;
head=(struct Node*)malloc(sizeof(struct Node*));
head->data=0;
head->next=NULL;
//初始化链表，貌似这个是头插法吧
for(int x=0;x<10;x++)
{
node1=(struct Node*)malloc(sizeof(struct Node*));
node1->data=x;
node1->next=head;
head=node1;
}
//输出原始链表
struct Node * pmove=head;
while (pmove)
{
if(pmove->next==NULL) break;
printf("%4d ",pmove->data);
pmove=pmove->next;
}
printf("\n");
//为了翻转链表，我们需要四个指针
struct Node * cur;
struct Node * next;
struct Node * pre; //还有一个是入口指针，前面有的
pre=cur=head;
next=cur->next;
cur->next=0;
while(1)
{
cur=next;
next=cur->next;
cur->next=pre;
pre=cur;
if (next==NULL) break;
}
//输出翻转后链表
pmove=cur->next;
while (pmove)
{
printf("%4d ",pmove->data);
pmove=pmove->next;
}
printf("\n");
return 0;
}
/*
输出案例：
PS D:\001> ./w1
9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9
PS D:\001>
*/

复制代码

wp231957 · 发表于 2022-5-8 13:29:36

wp231957 发表于 2022-5-8 13:05
第二稿：

这个版本用了尾插法，和头插法区别还是蛮大的（不像有些资料上说的没啥区别）

#include <stdio.h>
#include <malloc.h>
struct Node
{
int data;
struct Node *next;
};
int main()
{
struct Node * node1;
struct Node * head;
head=(struct Node*)malloc(sizeof(struct Node*));
head->data=0;
head->next=NULL;
struct Node * pmove=head;
struct Node * head2=head;
//初始化链表，准备使用尾插法
for(int x=0;x<10;x++)
{
node1=(struct Node*)malloc(sizeof(struct Node*));
node1->data=x;
node1->next=NULL;
head->next=node1;
head=node1;
}
//输出原始链表
pmove=pmove->next;
while (pmove)
{
printf("%4d ",pmove->data);
pmove=pmove->next;
}
printf("\n");
//为了翻转链表，我们需要四个指针
struct Node * cur;
struct Node * next;
struct Node * pre; //还有一个是入口指针，前面有的
pre=cur=head2;
next=cur->next;
cur->next=0;
while(1)
{
cur=next;
next=cur->next;
cur->next=pre;
pre=cur;
if (next==NULL) break;
}
//输出翻转后链表
pmove=cur;
while (pmove)
{
if(pmove->next==NULL) break;
printf("%4d ",pmove->data);
pmove=pmove->next;
}
printf("\n");
return 0;
}
/*
输出案例：
PS D:\001> ./w1
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
PS D:\001>
*/

复制代码

wp231957 · 发表于 2022-5-9 16:19:49

wp231957 发表于 2022-5-8 13:29
这个版本用了尾插法，和头插法区别还是蛮大的（不像有些资料上说的没啥区别）

半途翻转链表（不够完美，但是终于依靠自己的代码能翻了）

#include <stdio.h>
#include <malloc.h>
struct Node
{
int data;
struct Node *next;
};
int main()
{
struct Node * node1;
struct Node * head;
head=(struct Node*)malloc(sizeof(struct Node*));
head->data=0;
head->next=NULL;
//初始化链表，貌似这个是头插法吧
for(int x=0;x<10;x++)
{
node1=(struct Node*)malloc(sizeof(struct Node*));
node1->data=x;
node1->next=head;
head=node1;
}
//输出原始链表
struct Node * pmove=head;
while (pmove)
{
if(pmove->next==NULL) break;
printf("%4d ",pmove->data);
pmove=pmove->next;
}
printf("\n");
//获取出口节点和入口节点
struct Node * ennode=NULL;
struct Node * exitnode=NULL;
pmove=node1;
int i=1;
while (pmove)
{
if(i==3-1) ennode=pmove; //要在3节点翻转这里应该减一
if(i==6) exitnode=pmove;
pmove=pmove->next;
i++;
}
//半途翻转链表
struct Node * cur;
struct Node * next;
struct Node * pre;
//入口节点
cur=ennode; //此处ennode=node2
pre=next=ennode->next; //此处需要保存真正的入口地址
cur->next=exitnode; //跳转到需要翻转的首节点
//入口节点下一节点
cur=next;
next=next->next;
cur->next=exitnode->next; //跳转不需翻转的节点
pre=cur;
while(1)
{
cur=next;
next=next->next;
cur->next=pre;
pre=cur;
if (cur==exitnode) break;
}
//输出翻转后链表
pmove=head;
while (pmove)
{
if(pmove->next==NULL) break;
printf("%4d ",pmove->data);
pmove=pmove->next;
}
printf("\n");
return 0;
}
/*
附效果图:
PS D:\001> ./w1
9 8 7 6 5 4 3 2 1 0
9 8 4 5 6 7 3 2 1 0
PS D:\001>
*/

复制代码

wp231957 · 发表于 2022-5-10 10:37:32

wp231957 发表于 2022-5-9 16:19
半途翻转链表（不够完美，但是终于依靠自己的代码能翻了）

这里有个单链表循环链表的样例：

#include <stdio.h>
#include <malloc.h>
struct Node
{
int data;
struct Node *next;
};
//带头节点的头插法
struct Node * init_link(struct Node * s)
{
struct Node * head=s;
struct Node * tmp=NULL;
for(int x=10;x<20;x++)
{
struct Node * node1=NULL;
node1=(struct Node*)malloc(sizeof(struct Node*));
node1->data=x;
if(x==10) tmp=node1;
node1->next=head;
head=node1;
}
tmp->next=head; //构成循环链表，同时绕过头节点
return head;
}
int main()
{
struct Node * node1;
struct Node * head;
head=(struct Node*)malloc(sizeof(struct Node*));
head->data=0;
head->next=NULL;
//输出原始链表
struct Node * pmove=init_link(head);
int i=0;
while (pmove)
{
if(pmove->next==NULL) break;
printf("%4d ",pmove->data);
pmove=pmove->next;
i++;
if(i>15) break; //为了测试循环的效果我们选择了进行16次循环看一下效果
}
printf("\n");
return 0;
}
/*
附效果图:
PS D:\001> ./w3
19 18 17 16 15 14 13 12 11 10 19 18 17 16 15 14
*/

复制代码

wp231957 · 发表于 2022-5-10 10:41:22

wp231957 发表于 2022-5-10 10:37
这里有个单链表循环链表的样例：

不知道循环链表有啥用，估计是为了双循环链表打基础吧，看一下他的遍历退出条件

#include <stdio.h>
#include <malloc.h>
struct Node
{
int data;
struct Node *next;
};
//带头节点的头插法
struct Node * init_link(struct Node * s)
{
struct Node * head=s;
struct Node * tmp=NULL;
for(int x=10;x<20;x++)
{
struct Node * node1=NULL;
node1=(struct Node*)malloc(sizeof(struct Node*));
node1->data=x;
if(x==10) tmp=node1;
node1->next=head;
head=node1;
}
tmp->next=head; //构成循环链表，同时绕过头节点
return head;
}
int main()
{
struct Node * node1;
struct Node * head;
head=(struct Node*)malloc(sizeof(struct Node*));
head->data=0;
head->next=NULL;
//输出原始链表
struct Node * pmove=init_link(head);
struct Node * tmp=pmove;
while (pmove)
{
printf("%4d ",pmove->data);
if(pmove->next==tmp) break; //这里是循环链表的遍历退出条件
pmove=pmove->next;
}
printf("\n");
return 0;
}
/*
附效果图:
PS D:\001> ./w3
19 18 17 16 15 14 13 12 11 10
*/

复制代码

wp231957 · 发表于 2022-5-10 13:19:18

wp231957 发表于 2022-5-10 10:41
不知道循环链表有啥用，估计是为了双循环链表打基础吧，看一下他的遍历退出条件

前面都错了，也不改了，就那么地吧

这个版，功能是把一个链表插入另一个链表中间

#include <stdio.h>
#include <malloc.h>
struct Node
{
int data;
struct Node *next;
};
//带头节点的头插法
struct Node * init_link(struct Node * s)
{
struct Node * head=s;
for(int x=10;x<20;x++)
{
struct Node * node1=NULL;
node1=(struct Node*)malloc(sizeof(struct Node));
node1->data=x;
node1->next=head;
head=node1;
}
return head;
}
//带头节点的头插法
struct Node * init_link2(struct Node * s)
{
struct Node * head=s;
for(int x=100;x<110;x++)
{
struct Node * node1=NULL;
node1=(struct Node*)malloc(sizeof(struct Node));
node1->data=x;
node1->next=head;
head=node1;
}
return head;
}
int main()
{
struct Node * node1;
struct Node * head;
head=(struct Node*)malloc(sizeof(struct Node));
head->data=0;
head->next=NULL;
//输出原始链表
struct Node * pmove=init_link(head);
struct Node * ins_ennode=NULL;
struct Node * ins_exitnode=NULL;
int i=1;
struct Node * hhead=pmove;
while (pmove)
{
// printf("%4d ",pmove->data);
if(pmove->next==NULL) break;
if(i==3)
{
ins_ennode=pmove; //保存链表断开后的指针
ins_exitnode=pmove->next; //保存链表断开后的指针
break;
}
i++;
pmove=pmove->next;
}
struct Node * head2;
head2=(struct Node*)malloc(sizeof(struct Node));
head2->data=0;
head2->next=NULL;
struct Node * pmove2=init_link2(head2);
struct Node * sec_head=pmove2;
while (pmove2)
{
//printf("%4d ",pmove2->data);
if(pmove2->next->next==NULL) //把头节点绕出去
break;
pmove2=pmove2->next;
}
struct Node * sec_tail=pmove2;
//下面我们要做得就是把第二个链表插入第一个链表的第三个节点的后面
ins_ennode->next=sec_head;
sec_tail->next=ins_exitnode;
//遍历插入链表后的链表并输出
while (hhead)
{
if(hhead->next==NULL) break;
printf("%4d ",hhead->data);
hhead=hhead->next;
}
return 0;
}
/*
附效果图:
PS D:\001> ./w3
19 18 17 109 108 107 106 105 104 103 102 101 100 16 15 14 13 12 11 10
*/

复制代码

jhq999 · 发表于 2022-5-11 09:47:23

本帖最后由 jhq999 于 2022-5-11 09:51 编辑

wp231957 发表于 2022-5-10 13:19
前面都错了，也不改了，就那么地吧

这个版，功能是把一个链表插入另一个链表中间

#include <stdio.h>
#include <malloc.h>
struct Node
{
int data;
struct Node *next;
};
//带头节点的头插法
struct Node * init_link(struct Node * s)
{
struct Node * head=s;
for(int x=10;x<20;x++)
{
struct Node * node1=NULL;
node1=(struct Node*)malloc(sizeof(struct Node));
node1->data=x;
node1->next=head;
head=node1;
}
return head;
}
int main()
{
struct Node * node1;
struct Node * head;
head=(struct Node*)malloc(sizeof(struct Node));
head->data=0;
head->next=NULL;
//输出原始链表
head=init_link(head);
struct Node* p=head,*t=NULL;
while (p)
{
printf("%4d ",p->data);
p=p->next;
}
printf("\n");
p=t;
while (head)
{
t=head->next;
head->next=p;
p=head;
head=t;
}
head=p;
while (p)
{
printf("%4d ",p->data);
p=p->next;
}
while (head)
{
t=head->next;
free(head);
head=t;
}
return 0;
}

复制代码

19 18 17 16 15 14 13 12 11 10 0
0 10 11 12 13 14 15 16 17 18 19

复制代码

wp231957 · 发表于 2022-5-11 09:52:02

jhq999 发表于 2022-5-11 09:47

谢谢，我现在用不了电脑，我狠好奇，你另一个链表在哪里？？？

wp231957 · 发表于 2022-5-11 09:52:54

jhq999 发表于 2022-5-11 09:47

你这是倒序！

wp231957 · 发表于 2022-5-11 09:54:30

jhq999 发表于 2022-5-11 09:47

能帮忙写一段冒泡排序吗，？？我一直好奇，究竟是排指针啊，还是移动数据呢

jhq999 · 发表于 2022-5-11 12:02:35

本帖最后由 jhq999 于 2022-5-11 12:12 编辑

wp231957 发表于 2022-5-11 09:54
能帮忙写一段冒泡排序吗，？？我一直好奇，究竟是排指针啊，还是移动数据呢

不是链表反转吗，怎么还需要排序？
排序的话，感觉最好交换数据

wp231957 · 发表于 2022-5-11 12:19:12

jhq999 发表于 2022-5-11 12:02
不是链表反转吗，怎么还需要排序？
排序的话，感觉最好交换数据

翻转思路已经清晰了，就不用再研究了
你的思路我还需要研究一下

jhq999 · 发表于 2022-5-11 12:55:05

本帖最后由 jhq999 于 2022-5-11 16:24 编辑

wp231957 发表于 2022-5-11 12:19
翻转思路已经清晰了，就不用再研究了
你的思路我还需要研究一下

struct Node *end=NULL,*q;//////////没测试只是个思路
for (p=head; p->next; p=p->next)
{
for (q=head;q->next!=end;q=q->next)
{
if (q->data>q->next->data)
{
Node t=*q;
q->data=q->next->data;
q->next->data=t.data;
}
}
end=q;
}

复制代码

指针太麻烦了

struct Node list;
list.next=head;
while(1)
{
int flag=1;
for (prv=&list,q=list.next;q->next!=end;prv=q,q=q->next)
{
if (q->data>q->next->data)
{
flag=0;
prv->next=q->next;
q->next=prv->next->next;
prv->next->next=q;
q=prv->next;
}
}
//if (q!=list.next->next)
if(flag)
{
head=list.next;
break;
}
end=q;
}
head=list.next;

复制代码

wp231957 · 发表于 2022-5-11 17:11:56

jhq999 发表于 2022-5-11 12:55
指针太麻烦了

成功了，成功了，谢谢，那个交换指针的方案，我还是不要研究了（估计我研究不了）

#include <stdio.h>
#include <malloc.h>
#include <time.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node *next;
};
//带头节点的头插法
struct Node * init_link(struct Node * s)
{
srand((int)time(NULL));
struct Node * head=s;
for(int x=10;x<20;x++)
{
struct Node * node1=NULL;
node1=(struct Node*)malloc(sizeof(struct Node));
node1->data=rand()%10000;
node1->next=head;
head=node1;
}
return head;
}
int main()
{
struct Node * head;
head=(struct Node*)malloc(sizeof(struct Node));
head->data=0;
head->next=NULL;
head=init_link(head);
//输出原始链表
struct Node *pmove=head;
while (pmove)
{
if(pmove->next==NULL) break;
printf("%4d ",pmove->data);
pmove=pmove->next;
}
printf("\n");
//准备排序
struct Node *end=NULL,*q,*p;
for (p=head; p->next; p=p->next)
{
for (q=head;q->next!=end;q=q->next)
{
if (q->data>q->next->data)
{
int t=q->data;
q->data=q->next->data;
q->next->data=t;
}
}
end=q;
}
//输出排序后链表
pmove=head->next;
while (pmove)
{
printf("%4d ",pmove->data);
pmove=pmove->next;
}
return 0;
}
/*
样例输出:
PS D:\001> ./w4
8227 9821 3215 548 4427 2807 119 6152 7995 7628
119 548 2807 3215 4427 6152 7628 7995 8227 9821
*/

复制代码

wp231957 · 发表于 2022-5-13 15:18:26

wp231957 发表于 2022-5-11 17:11
成功了，成功了，谢谢，那个交换指针的方案，我还是不要研究了（估计我研究不了）

如果仅仅是为了逆序输出一个链表还可以更简单些：

void reverse_link(struct Node * head)
{
//这里正常是if(head==NULL) return; 这里我们使用带头节点的链表，所以把头节点绕过去
if(head->next==NULL) return;
reverse_link(head->next);
printf("%8d",head->data);
}

复制代码

账号		自动登录	找回密码
密码			立即注册

[技术交流] 链表翻转初稿

马上注册，结交更多好友，享用更多功能^_^

评分