一文读懂链表反转（迭代法和递归法）

2020 年 7 月 5 日
筆記
数据结构和算法

单向链表反转的方法有很多，其中用的比较多的是迭代法和递归法，迭代法通俗易懂，递归法相对来说比较难理解一些。

最近读了一些网上的文章对这两种算法的解释后，有些自己的理解分享出来供大家参考。

单向链表反转图示：

一、迭代法

迭代法的解题思路是：通过循环遍历的方式，使链表的每一个节点和它的下一个节点断开，然后重置其下一个节点。

代码实现：

import lombok.AllArgsConstructor;
import lombok.Data;

@Data
@AllArgsConstructor
public class ListNode {

    private int value;

    private ListNode next;


    /**
     * 迭代法
     * @param head
     * @return
     */
    public static ListNode reverseIterate(ListNode head){

        ListNode pre = null,cur = head,next = null;

        while (null != cur){
            next = cur.next;
            cur.next = pre; 
            pre = cur; 
            cur = next;
        }

        return pre;
    }

    public static void main(String[] args) {

        ListNode listNode4 = new ListNode(4, null);
        ListNode listNode3 = new ListNode(3, listNode4);
        ListNode listNode2 = new ListNode(2, listNode3);
        ListNode listNode1 = new ListNode(1, listNode2);

        System.out.println(reverseIterate(listNode1));
        
    }
}

代码解释：

对于链表中的一个节点(cur)来说，它包含节点的值（value）、其所指向的下一个节点（next）、及指向它的上一个节点（pre）。反转链表就是要把当前节点指向的下一个节点变成指向上一个节点。（链表头没有上一个节点，链表尾下一个节点的指向为空）

next = cur.next; 保留当前节点的下一个节点

cur.next = pre; 重置当前节点的下一个节点为上一个节点

pre = cur; 下次遍历需要用到的上一个节点

cur = next; 下次遍历需要用到的当前节点

其执行过程可以用下图表示：

迭代法的特点是：从前向后节点之间的链接依次断开，重置每个节点下一个节点的指向。

二、递归法

递归法的解题思路是：利用递归的思想和栈先进后出的特性，完成链表的反转。

要理解递归法，首先要对递归和栈的特性有一定的了解，这里简单介绍一下。

递归：方法自己调用自己、递归需要有结束条件。

栈:先进后出。

要牢记这两个点，对我们理解递归法很重要。

代码实现：

import lombok.AllArgsConstructor;
import lombok.Data;

@Data
@AllArgsConstructor
public class ListNode {

    private int value;

    private ListNode next;

    /**
     * 递归法
     * @param head
     * @return
     */
    public static ListNode reverseRecursion(ListNode head){
        if (null == head || null == head.next){
            return head;
        }

        ListNode newHead = reverseRecursion(head.next);

        head.next.next = head;
        head.next = null;

        return newHead;
    }


    public static void main(String[] args) {

        ListNode listNode4 = new ListNode(4, null);
        ListNode listNode3 = new ListNode(3, listNode4);
        ListNode listNode2 = new ListNode(2, listNode3);
        ListNode listNode1 = new ListNode(1, listNode2);

        System.out.println(reverseRecursion(listNode1));

    }
}

代码解释：

ListNode newHead = reverseRecursion(head.next);

1、递归法的目的是要返回一个新的头节点，这个新的头节点是原来链表的尾节点。

2、递归是方法自己调用自己，栈的特性是先进后出、后进先出。所以这段代码的作用是不断的去压栈。

head.next.next = head; 把当前节点指向的下一个节点的指向变为自己。（不要慌，这段代码的解释，下面有图有真相）

head.next = null; 当前节点指向的下一个节点变为空。

是不是看了上面的解释还有点不理解，别急，我第一次看这段代码的时候也是懵逼的（内心os:这写了个啥，怎么就反转链表了）

要理解这段代码首先，我们得去压几个栈，可能你会说我脑子里压不了几个栈容量就不够了，脑子就乱了，StackOverflowException。。。

讲真，我最开始也是想放弃的，背住代码算了。迭代法他就不香吗。。。

后来想到人类对图形的理解能力要长于文字，我们把这个过程画出来试试看能否理解。

我们还使用上文中使用过的链表作为数据源来分析这个过程