本文主要是介绍单链表反转与倒序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
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);}
}
总结:
链表反转也能够达到从尾都头输出单链表的效果,两者有什么区别呢?
链表反转会改变原链表的结构,指针指向以及头结点都会改变;
而从尾都头输出单链表并不改变链表的结构,借助栈或者递归实现将链表的值从尾都到头输出,可以看成是链表的值的反转。
这篇关于单链表反转与倒序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!