龙空技术网

面试现场:如何实现链表的逆序?

老田说编程 45

前言:

今天各位老铁们对“使用递归实现字符串的逆序输出”大体比较关心,我们都需要学习一些“使用递归实现字符串的逆序输出”的相关资讯。那么小编同时在网络上汇集了一些关于“使用递归实现字符串的逆序输出””的相关资讯,希望兄弟们能喜欢,我们一起来了解一下吧!

前几天一位小伙伴去面试,被要求现场写如何实现链表的逆序?写完一种问还有没有其他方式?

今天咱们就来聊聊到底如何实现链表的逆序以及有哪些方法?(文中的链表是单链表)

给定一个带头节点的单链表,请将其逆序。如下图所示,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语言如何将链表逆向 #链表逆向输出