1.1 如何实现链表的逆序
难度系数：★★★☆☆ 被考察系数：★★★★☆
题目描述：
给定一个带头结点的单链表，请将其逆序。即如果单链表原来为head-＞1-＞2-＞3-＞4-＞5-＞6-＞7，逆序后变为head-＞7-＞6-＞5-＞4-＞3-＞2-＞1。
分析与解答：
由于单链表与数组不同，单链表中每个结点的地址都存储在其前驱结点的指针域中，因此，对单链表中任何一个结点的访问只能从链表的头指针开始进行遍历。在对链表的操作过程中，需要特别注意在修改结点指针域的时候，记录下后继结点的地址，否则会丢失后继结点。
方法一：就地逆序
主要思路为：在遍历链表的时候，修改当前结点的指针域的指向，让其指向它的前驱结点。为此需要用一个指针变量来保存前驱结点的地址。此外，为了在调整当前结点指针域的指向后还能找到后继结点，还需要另外一个指针变量来保存后继结点的地址，在所有的结点都被保存好以后就可以直接完成指针的逆序了。除此之外，还需要特别注意对链表首尾结点的特殊处理。具体实现方式如下图所示。
在上图中，假设当前已经遍历到 cur 结点，而且它所有的前驱结点都已经完成了逆序操作，因此，只需要使cur-＞next=pre即可完成逆序操作，在此之前为了能够记录当前结点的后继结点的地址，需要用一个额外的指针next来保存后继结点的信息，通过上图（1）～（4）四步把实线的指针调整为虚线的指针就可以完成当前结点的逆序；当前结点完成逆序后，通过向后移动指针来对后续的结点用同样的方法进行逆序操作。算法实现如下：
程序的运行结果为
算法性能分析：
以上这种方法只需要对链表进行一次遍历，因此，时间复杂度为 O（n），其中，n 为链表的长度。但是需要常数个额外的变量来保存当前结点的前驱结点与后继结点，因此，空间复杂度为O（1）。
方法二：递归法
假定原链表为1-＞2-＞3-＞4-＞5-＞6-＞7，递归法的主要思路为：先逆序除第一个结点以外的子链表（将1-＞2-＞3-＞4-＞5-＞6-＞7变为1-＞7-＞6-＞5-＞4-＞3-＞2），接着把结点1添加到逆序的子链表的后面（1-＞2-＞3-＞4-＞5-＞6-＞7 变为 7-＞6-＞5-＞4-＞3-＞2-＞1）。同理，在逆序链表2-＞3-＞4-＞5-＞6-＞7时，也是先逆序子链表3-＞4-＞5-＞6-＞7（逆序为2-＞7-＞6-＞5-＞4-＞3），接着实现链表的整体逆序（2-＞7-＞6-＞5-＞4-＞3转换为7-＞6-＞5-＞4-＞3-＞2）。实现代码如下：
算法性能分析：
递归法也只需要对链表进行一次遍历，因此，算法复杂度也为 O（n），其中，n 为链表的长度。递归法的主要优点是：算法的思路比较直观，容易理解，而且也不需要保存前驱结点的地址；缺点是：算法实现的难度较大，此外，由于递归法需要不断地调用自己，需要额外的压栈与弹栈操作，因此，与方法一相比性能会有所下降。
方法三：插入法
插入法的主要思路为：从链表的第二个结点开始，把遍历到的结点插入到头结点的后面，直到遍历结束。假定原链表为head-＞1-＞2-＞3-＞4-＞5-＞6-＞7，在遍历到2 的时候，将其插入到头结点后，链表变为 head-＞2-＞1-＞3-＞4-＞5-＞6-＞7，同理将后序遍历到的所有结点都插入到头结点head后，就可以实现链表的逆序。实现代码如下：
算法性能分析：
以上这种方法也只需要对单链表进行一次遍历，因此，时间复杂度为 O（n），其中，n 为链表的长度。与方法一相比，这种方法不需要保存前驱结点的地址，与方法二相比，这种方法不需要递归的调用，效率更高。
引申：1）对不带头结点的单链表进行逆序
2）从尾到头输出链表
分析与解答：
对不带头结点的单链表的逆序读者可以自己练习（方法二已经实现了递归的方法），这里主要介绍单链表逆向输出的方法。
方法一：就地逆序+顺序输出
首先对链表进行逆序，然后顺序输出逆序后的链表。这个方法的缺点是改变了链表原来的结构。
方法二：逆序+顺序输出
申请新的存储空间，对链表进行逆序，然后顺序输出逆序后的链表。逆序的主要思路为：每当遍历到一个结点的时候，申请一块新的存储空间来存储这个结点的数据域，同时把新结点插入到新的链表的头结点后。这种方法的缺点是需要申请额外的存储空间。
方法三：递归输出
递归输出的主要思路为：先输出除当前结点外的后继子链表，然后输出当前结点，假如链表为：1-＞2-＞3-＞4-＞5-＞6-＞7，那么先输出 2-＞3-＞4-＞5-＞6-＞7，再输出 1。同理，对于链表2-＞3-＞4-＞5-＞6-＞7，也是先输出3-＞4-＞5-＞6-＞7，接着输出2，直到遍历到链表的最后一个结点7的时候会输出结点7，然后递归地输出6，5，…，1。实现代码如下：
算法性能分析：
以上这种方法只需要对链表进行一次遍历，因此，时间复杂度为 O（n），其中，n 为链表的长度。