单链表反转 指针坑
当我看到单链表反转这题目时,感觉这么简单啊。事实很多坑,一不小心就跳进去了。到现在我都记不清跳了多少坑。
写代码时不是死循环就是就是丢数据。 这 其实本质上是 指针的坑。一不留神就over了。
因为前面已经实现过各种列表的插入。
1、我首先想到的是从A链表中取出数据再生成一个新的链表B,从表头脑插入这样成了链表的反转了。
就顺手写了下面代码[1],运行进入死循环。
出现错误的原因:
假设,有 A->B->C->D->E这样一个链表
for循环中第一个head默认是A,h->next(A的指向的一个元素)是B。当然调用insert时 head作为参数传入。在insert方法里面参数node 等价于head。
所以node->next=head <=> head->next =head; 这样就造成死循环了。
又想当然的在reverse中定义了pre [2].照样出错。原因跟上面是一样的,head的next指向了自己。
还犯了一个错误就是单链表最后一个next没有赋值NULL,还有各种尝试就不在一一列举了,总之都是忽视指针指向错误。
[1]reverse代码片段 90 void reverse(void) 91 { 92 for(; head; head = head->next){ 93 insert(head); 94 } 95 } [2] 90 void reverse(void) 91 { 92 link pre = malloc(sizeof pre); 93 pre = head; 94 for(; pre; pre = pre->next){ 95 printf("%c\n", pre->element); 96 insert(pre); 97 } 98 } static link head; 66 void insert(link node) 67 { 68 if(head==NULL){ 69 tail = node; 70 } 71 node->next = head; 72 head = node; 73 } 74 1、重新构造一个head,当同时记住head的下一个元素,并把head的next设置为NULL. 循环遍历前,先取的head->next的对称赋值给curn。curn用来记录遍历位置,并把head的next设置为NULL. head会变成尾,这样保证尾节点指向NULL. 方法1、 void reverse(void) 163 { 164 link curn; 165 link temp; 166 if(head == NULL){ 167 return; 168 } 169 curn = head->next, 170 head->next = NULL; 171 while(curn != NULL){ 172 temp = curn; //保存当前节点 173 curn = curn->next; //改变curb指向下一个节点 174 temp->next = head; // 把head赋值给temp指向的节点 175 head = temp; //最后把temp赋值给head 176 } 177 return; 178 } 方法2、 这里实现使用把curn指向的下一个节点保存起来,curn指向的下一个节点改为指向head。然后把curn赋值给head,并把temp赋值给curn 142 void reverse(void) 143 { 144 link curn; 145 link temp; 146 if(head == NULL){ 147 return; 148 } 149 curn = head->next, 150 head->next = NULL; 151 while(curn != NULL){ 152 temp = curn->next; 153 curn->next = head; 154 head = curn; 155 curn = temp; 156 } 157 return; 158 } 159 方法3 1、如果head 或head->next为空直接返回 2、进入循环前需要先把pre赋值为NULL,防止出现链表尾元素为非空 99 void reverse(void) 100 { 101 link pre, cn; 102 if(head==NULL || head->next==NULL){ 103 return; 104 } 106 pre = NULL; 107 while(head->next){ 在循环中pre保存了每次遍历生成的新链表关系 108 cn = head->next; //保存 当前head节点指向的节点head->next 109 head->next = pre; //更改head指向 前一个pre保存的节点或NULL, 110 pre = head; //然后pre在保存当前head 111 head = cn; //最后从cn中循环中第一个语句保存的heade 指向的节点赋值给head 112 } 113 head->next = pre ; //退出循环后,head已经是最后一个节点,只需把head 的next指向pre既可 114 115 return; 116 }
相关推荐
已知head为单链表的表头指针,链表中存储的都是整形数据,实现下列运算的递归算法: (1)求链表中的最大值。 (2)求链表中的结点个数。 (3)求所有整数的平均值。
一、理解指针 看懂链表的结构并不是很难,但是一旦把它和指针混在一起,就很容易让人摸不着头脑。所以,要想写对链表代码,首先就要理解好指针。 有些语言有“指针”的概念,比如 C 语言;有些语言没有指针,...
设head为单链表的头指针,并设单链表带有头结点,编写算法将单链表中的数组元素按照其值递增有序的顺序进行就地排列
定义一个5个节点的单链表,然后通过指针的移动调换链表节点的顺序,从而实现链表的反转
设ha和hb分别是两个带头结点的非递减有序单链表的表头指针,试设计一个算法,将这两个有序链表合并成一个非递减有序的单链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其他的存储空间。表中允许有重复...
指针类型 11.1 指针 11.2 单链表 11.1 指针 11.2 单链表
本文档详细证实带环单链表快慢指针证明方法,其实难以理解的地方就是证明这个指针是如何追到它的
单链表操作中指针作为函数参数的典型错误.cpp
1.单链表反转 2.找出单链表的倒数第4个元素 3.找出单链表的中间元素 4.删除无头单链表的一个节点 5.两个不交叉的有序链表的合并 6.有个二级单链表,其中每个元素都含有一个指向一个单链表的指针。写程序把这个二级...
单链表反转 2.找出单链表的倒数第4个元素 3.找出单链表的中间元素 4.删除无头单链表的一个节点 5.两个不交叉的有序链表的合并 6.有个二级单链表,其中每个元素都含有一个指向一个单链表的指针。写程序把这个二...
运用二级指针在单链表中的删除操作的示例代码
带头结点的单链表,将其翻转,输出。typedef struct lnode { int data; struct lnode *next;/*指针域*/ } lnode,*linklist; /**linklist表示struct lnode类型的指针;lnode是别名*/
这两段代码都和指针有关,运行都会core。这样的两个坑也大概可以说明c++到底有多复杂,精通c++到底有多难。同时也大概可以说明为啥站在程序设计顶峰的人大抵都是c或c++程序员。
冒泡法反序排列无序单链表C和指针第十二章编程练习4,VC6.0编译通过,详细注释
在VC6.0环境下实现了使用尾指针创建循环单链表,输出第一个和最后一个节点的值
鼠标指针下载鼠标指针下载鼠标指针下载鼠标指针下载鼠标指针下载鼠标指针下载鼠标指针下载鼠标指针下载鼠标指针下载鼠标指针下载Yangcong WolfYangcong WolfYangcong WolfYangcong WolfYangcong WolfYangcong ...
彻底理解指针,指针数组和数组指针,指针函数和函数指针.doc
在Java中,判断单链表是否有环的经典方法是使用Floyd的“龟兔赛跑”算法,也称为快慢指针法。这种方法利用两个指针,一个每次走一步(称为慢指针),另一个每次走两步(称为快指针)。如果链表中存在环,那么快指针...
c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针...
C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针