单向链表的翻转

单向链表的翻转2014-07-11 iteye cq520单向链表翻转，之前把这个问题想的太简单了，以为只要把数据域翻转过来就可以了，结果是筐了大瓢，下面举一个简单的例子说明：

假设有n个人站成一排，现在要把这n个人的站的顺序颠倒过来，那么就不能只把这n个人的身高颠倒过来，而是要把每一个人的位置颠倒过来，第一个人站到最后，第二个人站倒数第二，以此类推。

为了检验程序的正确性，这一次我们打印时不能再打印结点数据，而要打印结点。Java程序运行时，JVM为程序开辟了内存空间，每一个结点在栈中都有一个保存的位置，要注意的是，每次程序运行时某一个结点在内存中保存的位置并不是一定的，所以进行方法测试的时候一定要在一次运行中进行测试，这也是之前我一直纠结的问题，为什么打印的结点元素对了，但是结点却不同。

下面来讲解一下我实现链表翻转的过程，在讲解正确方法之前先来看一下假翻转：

Java代码

public void wrongturn（）{for（int i=1;i<size（）;i++）{insert（i,get（size（））.obj）;delete（size（））;}}

这里的insert方法详见于我的上一篇博客当中

http://cq520.iteye.com/blog/1860061，这种做法的意思是，先把所有的结点都复制出来，再逆置插入链表中，每次插入之后就把最后一个多出来的结点删除掉，如果你只打印当前的链表元素很容易就被这种方法蒙蔽了，不过很明显，这种做法虽然能够达到逆置的效果，但是逆置的结点却全都变了，就像你换了一帮人来做这件事情一样，它们操作的内存地址不是同一块。

下面讲解正确的方法：

这是一个单链表：

1. 把尾结点放在首结点的前面，把首结点向后推移：

2. 把当前的最后一个结点依次插入到链表的下一个位置：