题目:定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。
假设有链表A->B->C->D->E->F->G。在反转链表过程中的某一阶段,其链表指针指向为:A<-B<-C<-D E->F->G。也就是说在结点D之前的所有结点都已经反转,而结点D后面的结点E开始的所有结点都没有反转。这样D跟E之间存在了断裂。我们如果要实现链表的反转,会有以下几个重要步骤:
- D->E变为D->C,指针反转
- 指针往后移动一个,操作下一个结点E
- 结合1.2我们发现需要操作3个指针,分别是C,D,E。
因此可以考虑存储C/D/E三个结点的指针,通过这三个结点的指针实现反转。
代码实例:
View Code
运行结果:
1
1 2 3 4 5 6 7
7 6 5 4 3 2 1
ps:2012-5-3
发现有一种更加简洁的写法,就是不需要pReversedHead指针,从上述程序我们可以看出来pReversedHead指针只是单纯的用来保存反转链表的头指针,但是pPrev和pNode指针其实就包含反转链表的头指针,因此我们没有必要单独定义一个头指针来保存。修改后的函数如下所示:
View Code
本文转自xwdreamer博客园博客,原文链接http://www.cnblogs.com/xwdreamer/archive/2012/04/26/2472797.html,如需转载请自行联系原作者