即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

C/C++_单链的快速逆置

编程语言 piupiuhao 10℃ 0评论

单链的快速逆置

1.首先我们应建立一个链表:

struct list{
 int data;
 list* next;
 };

这里用图解给出所建立的链表

然后用一个空的节点来指向我们链表的头结点,这个新节点存放

的数据为空,引用这个空节点来方便对后面的倒置进行操作

2.接下来是对链的倒置.

对每个元素来说,对应next的成员所存放的地址应该转移到原先链的下下一个元素的next中去,这样就完成了下下一个节点的逆置,


那么对应原先的链,我们应该从链首元素的上上一个元素所对应的next成员来找到链首的next成员的数值.而我们的链首元素的上上


一个元素不存在,所以我们将NULL赋值给首元素,而每次在赋值之前,我们应该将现有元素的next成员的值用一个中间变量保存起来


从而方便接下来的赋值操作.


在知道了如何进行转换之后,就可以写出如下代码:

list* x = NULL;        // 每次用来存储现有元素的NEXT的值
list* p = NEW->next;   // 用来遍历原来的链
list* y;        // 用来存放下一个要逆置的元素的首地址
while ( p ){           // 对循环进行判断,只要p不为空,就会对进行下一次逆置
 y = p->next;   // 先存好下一个要逆置的元素的首地址
 p->next = x;   // 改变现有元素的next成员
 x = p;         //存放下下一个元素的首地址,在下一次循环中赋值给对应元素的next成员
 p = y;        // 跟新循环判断条件并指向向下一个要逆置的元素
}
NEW->next = x;         // 要注意在完成逆置之后要将NEW元素的next改成逆置前的链的末元素的首地址

这样我们就完成了整个单链的快速逆置,只进行了一些地址的交换,而并没有繁琐的运算



转载请注明:CodingBlog » C/C++_单链的快速逆置

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情