本文主要是介绍单链表反转与倒序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1. 如何实现链表的反转
为了正确反转一个链表，需要调整指针指向。实现链表反转的过程中，需要注意两个问题：
在调整指针指向之前，必须先保存它原本指向的结点；
为了说明这个问题，我们先举个例子看一一下具体反转过程，例如， i，m，n是3个相邻的结点，假设经过若干步操作，已经把结点 i 之前的指针调整完毕。现在遍历到结点 m，当然，需要调整结点的 next 指针，让它指向结点 i，但需要注意的是，一旦调整了指针的指向，链表就断开了，因为已经没有指针指向结点 n，没有办法再遍历到结点 n 了，所以为了避免链表断开，需要在调整 m 的 next 之前把 n 保存下来。
找到反转后链表的头结点。
接下来试着找到反转后链表的头结点，不难分析出翻转后链表的头结点是原始链表的尾结点，即 next 为空指针的结点。
下面给出非递归方法实现链表的反转的代码：
public class Reverse {Node head;public void ReverseIteratively(Node head) {//链表反转Node pReverseHead = head;Node pNode = head;Node pPrev = null;while(pNode != null) {Node pNext = pNode.next;if(pNext == null)pReverseHead = pNode;pNode.next = pPrev;pPrev = pNode;pNode = pNext;}this.head = pReverseHead;}public void printReverseList() { // 遍历链表Node tmp = head;while(tmp != null) {System.out.print(tmp.data + " ");tmp = tmp.next;}System.out.println();}public static void main(String[] args) {MyLinkedList list = new MyLinkedList();Reverse reverse = new Reverse();list.addNode(5);list.addNode(3);list.addNode(2);list.addNode(6);list.printList();reverse.ReverseIteratively(list.head);System.out.println("反转后：");reverse.printReverseList();}
}/* Output:
5 3 2 6
反转后：
6 2 3 5
*///~
2. 如何从尾到头输出单链表
从头到尾输出单链表比较简单。要想解决本问题，很自然地想把链表中连接结点的指针反转过来，改变链表的方向，然后就可以从尾到头输出了。但该方法需要额外操作，是否有更好的方法呢？
2.1 利用栈( LIFO,后进先出 )存放遍历过的结点
从头到尾遍历链表，每经过一个结点，把该结点放到一个栈中。当遍历完整个链表后，再从栈顶开始输出结点的值，此时输出的结点的顺序已经翻转过来了。
// 遍历链表将所有结点的值存放在栈中
public static Stack<Integer> ListReverseStack(Node pListHead) {Stack<Integer> s = new Stack<Integer>();Node tmp = pListHead;while(tmp != null) {s.push(tmp.data);tmp = tmp.next;}return s;
}
// 打印栈中元素
public void printStack(Stack<Integer> s) {while(!s.isEmpty()) {System.out.print(s.pop() + " ");}System.out.println();
}该方法虽然只需要遍历一遍链表，但是需要维护一个额外的栈空间，实现起来比较麻烦。
2.2 递归实现
既然想到了栈来实现这个函数，而递归本质上就是一个栈结构，于是很自然地想到了用递归来实现。要实现反过来输出链表，每访问到一个结点，先递归输出它后面的结点，再输出该结点自身，这样链表的输出结果就反过来了。
//每访问到一个结点，先递归输出它后面的结点，再输出该结点自身
public void printListReversely(Node pListHead) {if(pListHead != null) {printListReversely(pListHead.next);System.out.println(pListHead.data);}
}总结：
链表反转也能够达到从尾都头输出单链表的效果，两者有什么区别呢？
链表反转会改变原链表的结构，指针指向以及头结点都会改变；
而从尾都头输出单链表并不改变链表的结构，借助栈或者递归实现将链表的值从尾都到头输出，可以看成是链表的值的反转。
这篇关于单链表反转与倒序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
![[数据结构]线性表之单链表的类模板实现](/front/images/it_default.gif)
