解析单链表逆置的多种方法

2017-03-29 21:17 阅读 3,001 次 评论 0 条

单链表的逆置还是很重要的,不过第一次写逆置的时候程序就直接奔溃了,因为解决与链表相关的问题总是有大量的指针操作,而指针操作的代码总是容易出错的,因此这也就成就了单链表在面试中的地位。

1.普通循环逆置

第一次循环后: ① pTemp指向Head  ② pCur指向P1  ③pTemp->pNext指向NULL。

第二次循环后: ① pTemp指向P1  ② pCur指向P2 ③pTemp->pNext指向Head。

第三次循环后: ① pTemp指向P2 ② pCur指向P3 ③ pTemp->pNext指向P1。

第四次循环后: ① pTemp指向P3 ② pCur指向NULL  ③ pTemp->pNext指向P2。

2.用三个指针逆置

分为两种情况:①链表为空或者链表中仅有一个节点,直接返回pHead ②链表中有多个节点时,利用三个指针的方法向后遍历,但是最后一个节点循环是进不去的,因此跳出循环需要单独处理。

3.头插法逆置

分为两种情况:①链表为空或者链表中仅有一个节点,直接返回pHead ②链表中有多个节点时:将pHead后面的节点依次插入到头结点的后面。

总体来说,我觉得三个指针的方法最容易理解,但容易出错,很多人都会忽视最后一个节点的特殊性,因此我建议大家在以后的使用与面试中最好使用头插法,头插法的原理很简单,只需要将新节点插入到头结点的后面即可。

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:解析单链表逆置的多种方法 | 术与道的分享
分类:编程素养 标签:,
1024do.com导航_术与道导航平台

发表评论


表情