ｃ语言链表逆序的问题 - bu_想 - 博客园
去面试被问到一个问题，怎么把一个链表反转(用原链表)，自己在网上找了到了一篇文章，http://blog.csdn.net/sicofield/article/details/8850269，原作者给出了三种方法，
方法一：将链表数据全部读到数组中，然后在倒序输出。
方法二：就是我下面要讲的。
方法三：从第二个结点开始，把之后的每个结点都插入到第一个结点之后，最后在把第一个结点挪到表尾。
第二种方法的思路是：从第二个结点开始，记录它的下个结点，把它挪到第一个结点之前，成为新表头，然后下个结点继续这个过程。
1 struct stu *reserve(struct stu *head)
struct stu *p1,*p2,*p3;
p2=p1-& // 这个结点为要移动的结点
p3=p2-& //记录的为要移动的结点的下一个结点
p2-&next=p1; //移动结点到最前
p1=p2; //移动的结点变为新表头
p2=p3; //下个结点变为要移动的结点
head-&next=NULL; //移动完毕后head变为表尾，让它指向为空
head=p1;
方法三的贴下原作者的代码加上自己的思路：
1 struct stu *reserve(struct stu *head)
struct stu *p,*q;
//记录第二个结点
while(p-&next!=NULL)
//记录要移动的结点
p-&next=q-&
//把该结点从原链表中移除
q-&next=head-&
//把该结点连接到head之后
head-&next=q;
//把head移动到新表尾，此时链表成环
head=p-&next-&
//找到移动完之后的新head
p-&next-&next=NULL;
阅读(...) 评论()查看: 1999|回复: 10
关于C语言中的链表问题
这个星期学习了链表~有些地方很不明白~想在这里提出来~望师兄给予指教~谢谢~
是这样的~学习了链表~现在大体能明白动态链表的实现了~但是如果要把原有的一个动态链表发序输出~应该怎么做呢?为此我看了些书~但是很不明白~因为没有图解~我不清楚为什么可以用P1,NEW两个指针指向最后一个结点,然后NEW会找得到一个NEXT~然后执行NEW-&NEXT=P1的赋值操作~再把NEW=P1;师兄们可以用个图解帮我理解一下~谢谢~
吴伟民老师的课件,还有他那本数据结构带的光盘就有了.
我去图书管看到那本书～但是没有光盘啊～可以在论坛上解释一下吗？
那本是教材.如果你们还没学这门课,去找师兄借
书上的没有反序的啊～我看过网上的很多教程～都教了怎么做～但是就是不明白～
图9：有N个节点的链表反序
单向链表的反序图示：
----&[1]----&[2]----&[3]...----&[n]----&[NULL]（原链表）
head& &1-&next&&2-&next&&3-&next& &n-&next
[NULL]&----[1]&----[2]&----[3]&----...[n]&----（反序后的链表）
& &&&1-&next&&2-&next&&3-&next& &n-&next&&head
结合原链表和插入后的链表，就很容易写出相应的代码。操作方法如下：
1、我们需要一个读原链表的指针p2,存反序链表的p1=NULL（刚好最后一个节点的next为NULL）,还有一个临时存储变量p；
2、p2在原链表中读出一个节点，我们就把它放到p1中，p就是用来处理节点放置顺序的问题；
3、比如，现在我们取得一个2,为了我们继续往下取节点，我们必须保存它的next值，由原链表可知p=2-&
4、然后由反序后的链表可知，反序后2-&next要指向1，则2-&next=1;
5、好了，现在已经反序一个节点，接着处理下一个节点就需要保存此时的信息：
& &p1变成刚刚加入的2，即p1=2;p2要变成它的下一节点，就是上面我们保存的p,即p2=p。
struct student *Reverse(struct student *head)
struct student *p; /*临时存储*/
struct student *p1; /*存储返回结果*/
struct student *p2; /*源结果节点一个一个取*/
p1 = NULL; /*开始颠倒时，已颠倒的部分为空*/
p2 = /*p2指向链表的头节点*/
while (p2 != NULL)
&&p = p2-&
&&p2-&next = p1;
&&p1 = p2;
head = p1;
这个图示很不清楚～我现在老是搞不明白怎么反过来～&&
&&p2-&next = p1;
&&p1 = p2;
这几句不明白～
p = p2-&
&&p2-&next = p1;
&&p1 = p2;
&&p2 =
复制代码
P2是从第一个开始遍历链表，而P1是紧跟着P2，且刚好是P2的前一个（在原链表来说）。
p2-&next = p1;就把链表反序了。
建议把 p1,p2,p 三个指针改成有代表意义的名字，有助于理解。
刚开始时是有点难理解的了，慢慢消化吧
如果有谁敢在代码里面加一些的这样的变量命名,
他会死的比较惨..
楼上，是不是应该再次把你的那张编程修养帖顶上来？
那当然不是这个意思..
又想起惨痛的经历...
实习的时候接了另外一个人的程序,一个函数上千行,命名变量a,b,f1,f2.....
我简直想吐血..
某大学的硕士毕业生？
Powered by1605人阅读
数据结构（19）
这里处理的全部是单链表:
typedef struct node {
char *data;
struct node *next;
我们约定一个打印链表的函数:
void list_display(node_t *head)
for (; head; head = head-&next)
printf(&%s &, head-&data);
printf(&\n&);
下面是几个常见的链表笔面问题:
1.计算链表长度
很简单:(复杂度O(n))
int list_len(node_t *head)
for (i = 0; head; head = head-&next, i++);
int main(int argc, const char *argv[])
node_t d = {&d&, 0}, c = {&c&, &d}, b = {&b&, &c}, a = {&a&, &b};
printf(&%d\n&, list_len(&a));//4
2.反转链表
我们多用几个指针就可以在O(n)完成反转任务:
算法:t遍历链表, q记录t的上一个结点, p是一个临时变量用来缓存t的值
void reverse(node_t *head)
node_t *p = 0, *q = 0, *t = 0;
for (t = head; t; p = t, t = t-&next, p-&next = q, q = p);
node_t d = {&d&, 0}, c = {&c&, &d}, b = {&b&, &c}, a = {&a&, &b};
list_display(&a);
reverse(&a);
list_display(&d);
3.查找倒数第k个元素(尾结点记为倒数第0个)
算法:2个指针p, q初始化指向头结点.p先跑到k结点处, 然后q再开始跑, 当p跑到最后跑到尾巴时, q正好到达倒数第k个.复杂度O(n)
node_t *_kth(node_t *head, int k)
int i = 0;
node_t *p = head, *q = head;
for (; p && i & k; p = p-&next, i++);
if (i & k) return 0;
for (; p-&next; p = p-&next, q = q-&next);
node_t d = {&d&, 0}, c = {&c&, &d}, b = {&b&, &c}, a = {&a&, &b};
printf(&_0 :%s _1: %s _2:%s _3:%s\n&, _kth(&a, 0)-&data, _kth(&a, 1)-&data, _kth(&a, 2)-&data, _kth(&a, 3)-&data);
_0 :d _1: c _2:b _3:a
4.查找中间结点
找出中间的那个结点
算法:设两个初始化指向头结点的指针p, q.p每次前进两个结点, q每次前进一个结点, 这样当p到达链表尾巴的时候, q到达了中间.复杂度O(n)
node_t *middle(node_t *head)
node_t *p, *q;
for (p = q = head; p-&next; p = p-&next, q = q-&next){
p = p-&next;
if (!(p-&next)) break;
node_t e = {&e&, 0}, d = {&d&, &e}, c = {&c&, &d}, b = {&b&, &c}, a = {&a&, &b};
printf(&%s\n&, middle(&a)-&data);
5.逆序打印链表
给你链表的头结点, 逆序打印这个链表.使用递归(即让系统使用栈), 时间复杂度O(n)
void r_display(node_t *t)
r_display(t-&next);
printf(&%s&, t-&data);
6.判断一个链表是否有环
如果一个链表有环, 那么它肯定只有一个环.(一个相交结点)
算法:设两个指针p, q, 初始化指向头.p以步长2的速度向前跑, q的步长是1.这样, 如果链表不存在环, p和q肯定不会相遇.如果存在环, p和q一定会相遇.(就像两个速度不同的汽车在一个环上跑绝对会相遇).复杂度O(n)
int any_ring(node_t *head)
node_t *p, *q;
for (p = q = head;p; p = p-&next, q = q-&next){
p = p-&next;
if (!p) break;
if (p == q) return 1; //yes
return 0; //fail find
node_t e = {&e&, 0}, d = {&d&, &e}, c = {&c&, &d}, b = {&b&, &c}, a = {&a&, &b};
e.next = &a;
printf(&%d\n&, any_ring(&a));
7.找出链表中环的入口结点
还是使用俩指针p和q, p扫描的步长为1, q扫描的步长为2.它们的相遇点为图中meet处(在环上).
假设头指针head到入口点entry之间的距离是K.则当q入环的时候, p已经领先了q为: d = K%n(n为环的周长).
我们设meet处相对entry的距离(沿行进方向)为x, 则有
(n-d)+x = 2x (p行进的路程是q的两倍)
解得x = n-d
那么当p和q在meet处相遇的时候, 从head处再发出一个步长为1的指针r, 可以知道, r和q会在entry处相遇!
初始化三个指针p, q, r全部指向head. 然后p以2的速度行进, q以1的速度行进.当p和q相遇的时候, 发出r指针并以1的速度行进, 当p和r相遇返回这个结点.复杂度O(n)
node_t *find_entry(node_t *head)
node_t *p, *q, *r;
for (p = q = head; p; p = p-&next, q = q-&next){
p = p-&next;
if (!p) break;
if (p == q) break;
if (!p) return 0; //no ring in list
for (r = head, q = q-&next; q != r; r = r-&next, q = q-&next);
node_t e = {&e&, 0}, d = {&d&, &e}, c = {&c&, &d}, b = {&b&, &c}, a = {&a&, &b};
e.next = &d;
printf(&%s\n&, find_entry(&a)-&data);
8.判断两个单链表是否相交
算法:两个指针遍历这两个链表,如果他们的尾结点相同,则必定相交.复杂度O(m+n)
int is_intersect(node_t *a, node_t *b)
if (!a || !b) return -1; //a or b is NULL
for (; a-&next; a = a-&next);
for (; b-&next; b = b-&next);
return a == b?1:0; //return 1 for yes, 0 for no
测试代码 :
node_t e = {&e&, 0}, d = {&d&, &e}, c = {&c&, &d}, b = {&b&, &c}, a = {&a&, &b};
node_t z = {&z&, &c}, y = {&y&, &z}, x = {&x&, &y};
printf(&%d\n&, is_intersect(&a, &x));
9.找两个链表相交的交点
假设两个链表a,b.a比b长k个结点(k&=0).
那么当a_ptr,b_ptr两个指针同时分别遍历a,b的时候, 必然b_ptr先到达结尾(NULL),而此时a_ptr落后a的尾巴k个结点.
如果此时再从a的头发出一个指针t,继续和a_ptr 一起走,当a_ptr达到结尾(NULL)时,t恰好走了k个结点.此时从b的头发一个指针s, s和t一起走,因为a比b长k个结点,所以,t和s会一起到达交点.
p,q分别遍历链表a,b,假设q先到达NULL,此时从a的头发出一个指针t,当p到达NULL时,从b的头发出s,当s==t的时候即交点.
代码实现:(注,当a,b不相交,函数返回0,即相交在NULL)
node_t *intersect_point(node_t *a, node_t *b)
node_t *p, *q, *k, *t, *s;
for (p = a, q = b; p && q; p = p-&next, q = q-&next);
k = (p == 0)?q:p; //k record the pointer not NULL
t = (p == 0)?b:a; //if p arrive at tail first, t = else p = a
s = (p == 0)?a:b;
for (; k; k = k-&next, t = t-&next);
for (; t != s; t = t-&next, s = s-&next);
node_t e = {&e&, 0}, d = {&d&, &e}, c = {&c&, &d}, b = {&b&, &c}, a = {&a&, &b};
node_t z = {&z&, &b}, y = {&y&, &z}, x = {&x&, &y};
printf(&%s\n&, intersect_point(&a, &x)-&data);
10.O(1)删除结点(不给头结点)
其实我很反对这个做法.
不给头结点的时候怎么删除一个结点d:
把d的下一个结点e的数据拷贝到d中,然后删除e
我认为这是个伪删除,并且这个算法无法处理d是最后一个结点的情况
node_t *delete(node_t *d)
node_t *e = d-&next;
d-&data = e-&data;
d-&next = e-&next;
11.两个链表右对齐打印
为了打印的整齐性,我们把结点存储的数据类型改为int(我们存放数字)
比如两个链表1-&2-&3-&4-&5和6-&7-&8,我们想要打印这种效果:
p和q两个指针分别遍历链表a和b,假如q先到达0(即a比b长),此时由a头发出t,打印完链表a.
p继续移动到0,并打印空格.
从b头发出指针s打印链表b
void foo(node_t *a, node_t *b)
node_t *p, *q, *k, *t, *s;
for (p = a, q = b; p && q; p = p-&next, q = q-&next);
k = p?p:q;
t = p?a:b;
s = p?b:a;
for (; t; printf(&%d &, t-&data), t = t-&next);
printf(&\n&);
for (; k; printf(&
&), k = k-&next);
for (; s; printf(&%d &, s-&data), s = s-&next);
node_t e = {5, 0}, d = {4, &e}, c = {3, &d}, b = {2, &c}, a = {1, &b};
o = {8, 0}, n = {7, &o}, m = {6, &n};
foo(&a, &m);
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：215638次
积分：3985
积分：3985
排名：第6637名
原创：163篇
转载：45篇
评论：36条
文章：16篇
阅读：14770
文章：18篇
阅读：30604新手园地& & & 硬件问题Linux系统管理Linux网络问题Linux环境编程Linux桌面系统国产LinuxBSD& & & BSD文档中心AIX& & & 新手入门& & & AIX文档中心& & & 资源下载& & & Power高级应用& & & IBM存储AS400Solaris& & & Solaris文档中心HP-UX& & & HP文档中心SCO UNIX& & & SCO文档中心互操作专区IRIXTru64 UNIXMac OS X门户网站运维集群和高可用服务器应用监控和防护虚拟化技术架构设计行业应用和管理服务器及硬件技术& & & 服务器资源下载云计算& & & 云计算文档中心& & & 云计算业界& & & 云计算资源下载存储备份& & & 存储文档中心& & & 存储业界& & & 存储资源下载& & & Symantec技术交流区安全技术网络技术& & & 网络技术文档中心C/C++& & & GUI编程& & & Functional编程内核源码& & & 内核问题移动开发& & & 移动开发技术资料ShellPerlJava& & & Java文档中心PHP& & & php文档中心Python& & & Python文档中心RubyCPU与编译器嵌入式开发驱动开发Web开发VoIP开发技术MySQL& & & MySQL文档中心SybaseOraclePostgreSQLDB2Informix数据仓库与数据挖掘NoSQL技术IT业界新闻与评论IT职业生涯& & & 猎头招聘IT图书与评论& & & CU技术图书大系& & & Linux书友会二手交易下载共享Linux文档专区IT培训与认证& & & 培训交流& & & 认证培训清茶斋投资理财运动地带快乐数码摄影& & & 摄影器材& & & 摄影比赛专区IT爱车族旅游天下站务交流版主会议室博客SNS站务交流区CU活动专区& & & Power活动专区& & & 拍卖交流区频道交流区
稍有积蓄, 积分 230, 距离下一级还需 270 积分
论坛徽章:0
#include &stdio.h&
#include &stdlib.h&
#include &string.h&
struct student{
& &&&char *
typedef struct student STU;
struct Node{
& & struct Node *
typedef struct Node NODE;
//链表的初始化
NODE *init_Node(NODE *L)
& & L=(NODE *)malloc(sizeof(NODE));
& & if(!L) printf(& L is NULL\n&);
& && &memset(&(L-&Data),0,sizeof(STU));
& && &printf(&name:%s,score:%lf\n&,L-&Data.name,L-&Data.sore);
& && &L-&next=NULL;
& && &printf(&0x%x\n&,L-&next);
& &return L;
//链表的添加
int&&Listinserth(NODE *L,STU data)
& & & & NODE *H;
& & & & H=L;
& & & & while(H)
& & & && &printf(&调试H-&Data.name=%s\n,调试：H-&Data.sore=%lf\n&,H-&Data.name,H-&Data.sore);
& & & && &H=H-&
& & & & if(!H)
& && && && & H=(NODE *)malloc(sizeof(NODE));
& & & & & & & & & &&&H-&Data=
& & & & & & & & & &&&H-&next=NULL;
& & & & & & & & & &&&printf(&No to successful\n&);
& && & & &&&}
&&& & & &&&else
& & & & & & & & {
& & & & & & & &&&H-&Data=
& & & & & & & &&&H-&next=NULL;
& & & & & & & &&&printf(& exist to exist!&);
& & & & & & & & }
& & & &&&printf(&调试H-&Data.name=%s\n,调试：H-&Data.sore=%lf\n&,H-&Data.name,H-&Data.sore);
//& & & & NODE *S;
//& & & & S=H;
//& & & & while(H)
//& & & & {
//& & & & printf(&H-&Data.name:%s,H-&Data.sore:%lf\n&,H-&Data.name,H-&Data.sore);
//& & & & H=H-&
//& & & & }
//& & & & if(!H)
// & & & & & & & & printf(&H is null\n&);
//& & & & H=S;
& & & & return 0;
//输出链表
void DisplayList(NODE *p)
& & & & NODE *q;
& & & & q=p;
& & & & printf(&我就不相信没有东西输出：\n&);
& & & & if(q==NULL)
& & & & & & & & printf(&P is NULL \n&);
& & & & else
& && && && && & while(q)
& && && && && &{
& && &&&& & & && && & printf(&name:%s, sore:%lf\n&,q-&Data.name,q-&Data.sore);
& && &&&& & & && && & q=q-&
& && && && && &}
int main(int argc,char *argv[])
& &&&NODE *p;
& &&&p=init_Node(p);
& &&&printf(&P_init:0x%x\n&,p);
& &&&printf(&name:%s,score:%lf\n&,p-&Data.name,p-&Data.sore);
& &&&STU data1;
& &&&data1.name=&duwei&;
& &&&//strcpy(data1.name,&duwei&);
& &&&data1.sore=145.50;
& &&&printf(&p1:0x%x\n&,p);
& &&&Listinserth(p,data1);
& &&&printf(&p2:0x%x\n&,p);
& &&&DisplayList(p);
& &&&STU data2;
& &&&data2.name=&hello world&;
& &&&data2.sore=146.85;
& &&&Listinserth(p,data2);
& &&&printf(&p address:0x%x\n&,p);
& &&&DisplayList(p);
& &&&printf(&add successfully\n&);
& &&&return 0;
这个是我代码：我实现的是在链表尾部插入一个结点，并将整个链表输出：
有个问题在插入函数，我知道是什么问题，希望高手帮忙解决下，最好能提供解决方法
& |& & |& & |& & |& 
稍有积蓄, 积分 230, 距离下一级还需 270 积分
论坛徽章:0
来个人帮帮忙行不
稍有积蓄, 积分 230, 距离下一级还需 270 积分
论坛徽章:0
有人吗，我纠结了好几天了，都不知道怎么修改，谁帮我看看啊
丰衣足食, 积分 595, 距离下一级还需 405 积分
论坛徽章:0
添加链表元素中，现在的做法是直接把一个 STU 实例复制给另外一个： H-&Data=data ，这个赋值会起作用么？
既然 NODE 中已经包含了一个 STU 的实例，那么在链表的插入中，应该对这个实例中的每一个成员变量分别赋值。
if(!H)
& & {
& && &&&H=(NODE *)malloc(sizeof(NODE));
& && &&&H-&Data.name=data.
& && &&&H-&Data.sore = data.
& && &&&printf(&Name: %s, score: %lf\n&, H-&Data.name, H-&Data.sore);
& && &&&H-&next=NULL;
& & }
复制代码其实，在 NODE 中直接嵌入一个 STU 的指针，然后向链表中插入数据的时候也传指针会更好一些。起码少好几次 malloc 。
家境小康, 积分 1421, 距离下一级还需 579 积分
论坛徽章:0
这是由于你在插入节点的时候没有将上一个节点的 next 指针指向节点。
大富大贵, 积分 15884, 距离下一级还需 4116 积分
论坛徽章:0
插入算法基本模式
Node *pNew = new N
memset(pNew, 0, sizeof(Node));
Node *p = pH
while(p-&pNext != NULL)
& & p = p-&pN
p-&pNext = pN
pNew-&pNext = NULL;
稍有积蓄, 积分 230, 距离下一级还需 270 积分
论坛徽章:0
5楼的正解，谢谢!!!
谢谢大家！！
富足长乐, 积分 5817, 距离下一级还需 2183 积分
论坛徽章:0
慢慢跟踪，总会发现问题的
稍有积蓄, 积分 230, 距离下一级还需 270 积分
论坛徽章:0
谢谢5楼和6楼，非常感谢，OK了，哎，我现在多是下班自己学这个，工作和这个不想干，所以没什么时间，你们帮我节省了大量时间，真的非常感谢，有机会请你们吃饭，哈哈
白手起家, 积分 59, 距离下一级还需 141 积分
论坛徽章:0
本帖最后由 fifa2002nb 于
21:29 编辑
北京皓辰网域网络信息技术有限公司. 版权所有 京ICP证:060528号 北京市公安局海淀分局网监中心备案编号：
广播电视节目制作经营许可证(京) 字第1234号
中国互联网协会会员&&联系我们：
感谢所有关心和支持过ChinaUnix的朋友们
转载本站内容请注明原作者名及出处
