面试现场:如何实现链表的逆序? 链表逆置是什么意思

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

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

给定一个带头节点的单链表，请将其逆序。如下图所示，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为链表的长度。