前言:
今天各位老铁们对“使用递归实现字符串的逆序输出”大体比较关心,我们都需要学习一些“使用递归实现字符串的逆序输出”的相关资讯。那么小编同时在网络上汇集了一些关于“使用递归实现字符串的逆序输出””的相关资讯,希望兄弟们能喜欢,我们一起来了解一下吧!前几天一位小伙伴去面试,被要求现场写如何实现链表的逆序?写完一种问还有没有其他方式?
今天咱们就来聊聊到底如何实现链表的逆序以及有哪些方法?(文中的链表是单链表)
给定一个带头节点的单链表,请将其逆序。如下图所示,head为头部。
由于单链表与数组不相同,单链表中每个节点的地址都存储在其前驱节点的指针域中,因此,对单链表中任何一个结点的访问只能从链表的头指针开始进行遍历。在对链表的操作过程中,需要特别注意在修改结点指针域的时候,记录下后继结点的地址,否则会丢失后继结点。
方法一:就地逆序
序主要思路:在遍历链表时,修改当前结点的指针域的指向,让其指向它的前驱结点。为此,需要用一个指针变量来保存前驱结点的地址。此外,为了在调整当前结点指针域的指向后还能找到后继结点,还需要另外一个指针变量来保存后继结点的地址,在所有的结点都被保存好以后就可以直接完成指针的逆序了。除此之外,还需要特别注意对链表首尾结点的特殊处理。具体实现方式如下图所示。
在上图中,假设当前已经遍历到cur 结点,由于它所有的前驱结点都已经完成了逆序操作,因此,只需要使
cur.next=pre
即可完成逆序操作。在此之前,为了能够记录当前结点的后继结点的地址,需要用一个额外的指针next来保存后继结点的信息,通过上图(1)~(4)四步把实线的指针调整为虚线的指针就可以完成当前结点的逆序;当前结点完成逆序后,通过向后移动指针来对后续的结点用同样的方法进行逆序操作。
算法实现
//节点信息public class Node { public int data; public Node next;}public class NodeReversal { public static void main(String[] args) { Node head = new Node(); head.next = null; Node temp = null; Node cur = head; for (int i = 0; i < 8; i++) { temp = new Node(); temp.data = i; temp.next = null; cur.next = temp; cur = temp; } System.out.println("逆序之前"); for (cur = head.next; cur != null; cur = cur.next) { System.out.print(cur.data + " "); } reversal(head); System.out.println(); System.out.println("逆序之后"); for (cur = head.next; cur != null; cur = cur.next) { System.out.print(cur.data + " "); } } public static void reversal(Node head) { //如果头结点为空或者只有一个头结点,就不用反转了 if (head == null || head.next == null) { return; } //前驱节点 Node pre = null; //当前节点 Node cur = null; //后继节点 Node next = null; //把链表首节点变为尾节点 cur = head.next; next = cur.next; cur.next = null; pre = cur; cur = next; //使当前遍历到的结点cur指向前驱节点 while (cur.next != null) { next = cur.next; cur.next = pre; pre = cur; cur = cur.next; cur = next; } //节点最后一个结点指向倒数第二个节点 cur.next = pre; //链表的头及诶单指向原来链表的尾节点 head.next = cur; }}
运行结果
逆序之前0 1 2 3 4 5 6 7逆序之后7 6 5 4 3 2 1 0算法性能分析
以上这种方法只需要对链表进行一次遍历,因此,时间复杂度为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)。
算法实现
public class NodeReversal { public static void main(String[] args) { Node head = new Node(); head.next = null; Node temp = null; Node cur = head; for (int i = 0; i < 8; i++) { temp = new Node(); temp.data = i; temp.next = null; cur.next = temp; cur = temp; } System.out.println("逆序之前"); for (cur = head.next; cur != null; cur = cur.next) { System.out.print(cur.data + " "); } reverse(head); System.out.println(); System.out.println("逆序之后"); for (cur = head.next; cur != null; cur = cur.next) { System.out.print(cur.data + " "); } } public static Node recursionReversal(Node head) { if (head == null || head.next == null) { return head; } //反转后面的节点 Node newHead = recursionReversal(head.next); //把当前遍历的节点加到后面节点逆序后链表的尾部 head.next.next = head; head.next = null; return newHead; } /** * 方法功能:对待头节点的单链表进行逆序 * * @param head head链表头节点 */ public static void reverse(Node head) { if (head == null) { return; } //获取链表的第一个节点 Node firstNode = head.next; //对链表进行逆序 Node newHead = recursionReversal(firstNode); //头节点指向逆序后链表的第一个节点 head.next = newHead; }}
运行输出
逆序之前0 1 2 3 4 5 6 7逆序之后7 6 5 4 3 2 1 0算法性能分析
由于递归法也只需要对链表进行一次遍历,因此,算法的时间复杂度也为O(N)。其中, N 为链表的长度。递归法的主要优点是:思路比较直观,容易理解,而且也不需要保存前驱结点的地址;缺点是:算法实现的难度较大。此外,由于递归法需要不断地调用自己,需要额外的压栈与弹栈操作,因此,与方法一相比性能会有所下降。
方法三:插入法
插入法的主要思路:从链表的第二个结点开始,把遍历到的结点插入到头结点的后面,直到遍历结束。假定原链表为
head→1→2→3→4→5→6→7
在遍历到2时,将其插入到头结点后,链表变为
head→2→1→3→4→5→6→7
同理将后序遍历到的所有结点都插入到头结点head后,就可以实现链表的逆序。
算法实现
public class NodeReversal { public static void main(String[] args) { Node head = new Node(); head.next = null; Node temp = null; Node cur = head; for (int i = 0; i < 8; i++) { temp = new Node(); temp.data = i; temp.next = null; cur.next = temp; cur = temp; } System.out.println("逆序之前"); for (cur = head.next; cur != null; cur = cur.next) { System.out.print(cur.data + " "); } reversal(head); System.out.println(); System.out.println("逆序之后"); for (cur = head.next; cur != null; cur = cur.next) { System.out.print(cur.data + " "); } } public static void reversal(Node head) { //判断链表是否为空 if (head == null || head.next == null) { return; } //当前节点 Node cur = null; //后排节点 Node next = null; cur = head.next.next; //设置链表第一个节点为尾节点 head.next.next = null; //把遍历到节点插入到头节点的后面 while (cur != null) { next = cur.next; cur.next = head.next; head.next = cur; cur = next; } }}
算法性能分析
以上这种方法也只需要对单链表进行一次遍历,因此,时间复杂度为O(N)。其中,N为链表的长度。与方法一相比,这种方法不需要保存前驱结点的地址,与方法二相比,这种方法不需要递归地调用,效率更高。
引申
①对不带头结点的单链表进行逆序;
②从尾到头输出链表。
分析
对不带头结点的单链表的逆序,读者可以自己练习(方法二已经实现了递归的方法),这里主要介绍单链表逆向输出的方法。
方法一:就地逆序+顺序输出
首先对链表进行逆序,然后顺序输出逆序后的链表。这种方法的缺点是改变了链表原来的结构。
方法二:逆序+顺序输出
申请新的存储空间,对链表进行逆序,然后顺序输出逆序后的链表。逆序的主要思路为:每当遍历到一个结点的时候,申请一块新的存储空间来存储这个结点的数据域,同时把新结点插入到新的链表的头结点后。这种方法的缺点是需要申请额外的存储空间。
方法三:递归输出
递归输出的主要思路:先输出除当前结点外的后继子链表,然后输出当前结点,假如链表为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。实现代码如下:
public class NodeReversal { public static void main(String[] args) { Node head = new Node(); head.next = null; Node temp = null; Node cur = head; //制造链表0->1->2->3->4->5->6->7 for (int i = 0; i < 8; i++) { temp = new Node(); temp.data = i; temp.next = null; cur.next = temp; cur = temp; } System.out.println("逆序之前"); for (cur = head.next; cur != null; cur = cur.next) { System.out.print(cur.data + " "); } System.out.println(); System.out.println("逆序之后"); reversal(head.next); } public static void reversal(Node firstNode) { if (firstNode == null) { return; } reversal(firstNode.next); System.out.print(firstNode.data + " "); }}
输出
逆序之前0 1 2 3 4 5 6 7逆序之后7 6 5 4 3 2 1 0
算法性能分析:以上这种方法只需要对链表进行一次遍历,因此,时间复杂度为O(N)。其中,N为链表的长度。
标签: #使用递归实现字符串的逆序输出 #链表逆序与反转有什么区别 #c语言如何将链表逆向 #链表逆向输出