有关链表逆序

给你一个链表，然后需要把链表给逆序输出，而且不能用交换链表的值或者新建一个链表的方式。

1. 把一个链表从头到尾全部逆序，这个应该算这一些列问题里面最基本的东西了。大致思路就是每次把一个链表的当前node和next node给反过来，然后你需要记录下一个处理的节点是哪个，也就是处理完当前节点，需要往后移动一个。直接上代码：

上面的代码就是把链表逆序的核心代码了，当然最后你还需要处理链表的头节点什么的。首先我们用p和q两个指针指向当前节点，和原链表中的下一个节点，如果下一个节点为NULL的话，我们就直接退出循环了，因为这里不需要逆序了。对于p和q，我们首先记录下q的下一个节点t，因为待会我们会把q的next指针更新为p也就是逆序，如果不记录下q的下一个节点，那么这个节点我们就再也访问不到了。然后将q的next指针指向p（对链表进行逆序），然后将p更新为q，q更新为t，也就是说处理原链表中p的下一个节点。这个处理完了之后，链表基本已经逆序了，为什么说基本呢？可以看一个例子：1->2->3->4，用上述算法处理完成之后将变成1->2, 2->1, 3->2, 4->3，也就是说1和3都指向2，而没有指针指向4，但是4现在是表头。所以这里我们需要对原链表的表头和表尾进行处理。

这里root是原链表的表头，也就是新链表的表尾，所以它的next就是NULL，同时更新表头节点，经过while循环之后，p指向的是原链表的最后一个节点，当然就是新链表的头节点了。到此，链表逆序也就完成了。不过这只是基本的链表逆序而已，下面有两个变种。

2. 给定一个链表，然后给定两个数m和n，1<=m<=n<=length，length是链表的长度。你需要把链表中从第m个到第n个元素给逆序。这里大致思路还是和上面的差不多，不过处理的是链表的一部分，而不是全部，这个会比上面稍微的麻烦一点。上面我们在while循环之后加了两句话用来更新头节点和尾节点，那么同样我们这里需要更新类似的“头节点”和“尾节点”，比如1->2->3->4->5，m=2，n=4，的话，我们要在逆序之后，使得1指向4，而2指向5，这就是我们这里的“头节点”和“尾节点”，对于2指向5这个问题还是比较好处理的，因为我们能够找到2和5，这样的话直接加上一句就行了，然后把1指向4的话，我们需要保存节点2的前一个节点，这里我们需要保存每个节点的前一个节点，这样的话，我们才能够使得最后让1（2的前一个节点）指向4.不过这里有一个小小的trick，也就是说如果当前节点没有前一个节点（m=1），那么我们需要特殊处理一下，同样我们需要更新链表的头节点。具体的代码可以参照这里。

3. 如果给定一个链表，然后给定一个数n，让你把链表分成n个节点一段，每一段里面进行逆序，如果最后没有n个节点的话，那么就保持原样，比如1->2->3->4->5，然后n=2，处理完之后应该是2->1->4->3->5.这个问题，比上面两个要更复杂，首先你不能顺序依次处理过去，因为如果依次处理过去的话，段之间的链接就不对了，可以用笔画一下，依次处理过去的时候，2的下一个节点是不好指向4的，因为3->4这一段还没有逆序，但是最后我们需要的是2指向4，而不是3.这里就需要我们从后往前处理了，也就是说我们必须把当前段后面的所有段都已经处理完成了，然后再处理当前段，比如我们处理3->4的时候，5必须处理好（单个节点不需要好处理），然后处理1->2的时候，3->4->5必须处理好了，也就是变成了4->3->5.这样就满足递归的性质了，我们可以把这个问题用递归的方法写出来，先找到一段，然后处理这一段的后面所有段，然后再处理当前段，这样的话，我们就保证了处理当前段的时候，后面的已经是处理好了。具体代码可以参考这里。