理解单链表的反转(java实现)

秒速五厘米 2021-05-27 20:38 419阅读 0赞

要求很简单，输入一个链表，反转链表后，输出新链表的表头。  
  反转链表是有2种方法(递归法，遍历法)实现的，面试官最爱考察的算法无非是斐波那契数列和单链表反转，递归方法实现链表反转比较优雅，但是对于不了解递归的同学来说还是有理解难度的。

## 递归法 ##

总体来说，递归法是从最后一个Node开始，在弹栈的过程中将指针顺序置换的。

![éå½æ³å®ç°å¾][format_png]

为了方便理解，我们以 1->2->3->4这个链表来做演示。输出的效果是4->3->2->1

**首先定义Node：**

public static class Node {
        public int value;
        public Node next;
    
        public Node(int data) {
            this.value = data;
        }
    }

反转方法如下：

public Node reverse(Node head) {
        if (head == null || head.next == null)
            return head;
        Node temp = head.next;
        Node newHead = reverse(head.next);
        temp.next = head;
        head.next = null;
        return newHead;
    }

递归实质上就是系统帮你压栈的过程，系统在压栈的时候会保留现场。

我们来看是怎样的一个递归过程：1->2->3->4

*  程序到达Node newHead = reverse(head.next);时进入递归
 *  我们假设此时递归到了3结点，此时head=3结点，temp=3结点.next(实际上是4结点)
 *  执行Node newHead = reverse(head.next);传入的head.next是4结点，返回的newHead是4结点。
 *  接下来就是弹栈过程了
    
     *  程序继续执行 temp.next = head就相当于4->3
     *  head.next = null 即把3结点指向4结点的指针断掉。
     *  返回新链表的头结点newHead

注意：当return后，系统会恢复2结点压栈时的现场，此时的head=2结点；temp=2结点.next(3结点)，再进行上述的操作。最后完成整个链表的翻转。

## 遍历法 ##

![enter image description here][]

public static Node reverseList(Node node) {
      Node pre = null;
      Node next = null;
      while (node != null) {
          next = node.next;
          node.next = pre;
          pre = node;
          node = next;
      }
      return pre;
    }

*  依旧是1->2->3->4
 *  准备两个空结点 pre用来保存先前结点、next用来做临时变量
 *  在头结点node遍历的时候此时为1结点
    
     *  next = 1结点.next(2结点)
     *  1结点.next=pre(null)
     *  pre = 1结点
     *  node = 2结点
 *  进行下一次循环node=2结点
    
     *  next = 2结点.next(3结点)
     *  2结点.next=pre(1结点)=>即完成2->1
     *  pre = 2结点
     *  node = 3结点
 *  进行循环...

[format_png]: /images/20210527/746256db79104990b4e4dd5694953af7.png
[enter image description here]: /images/20210527/2a6156cb64834d6eba55fb0c60f98cca.png