力扣206. 【反转链表】的三种实现方式：头插法，迭代法，递归法（附带Java实现和讲解视频链接）_力扣反转链表用头插法

题目描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

头插法实现

对链表有了解的小伙伴应该对头插法建立单链表的方法有所了解，头插法的特征是，建立好的单链表的顺序和我们输入节点的顺序是相反的，按这个特种，我们就可以借助头插法对链表进行逆置

public ListNode reverseList(ListNode head) {
        ListNode ans = null;
        //遍历链表,并用头插法完成逆置
        for (ListNode current = head; current != null; current = current.next) {
            ans = new ListNode(current.val, ans);
        }
        return ans;
    }
1
2
3
4
5
6
7
8

迭代与递归的预备知识

递归（recursion）：递归常被用来描述以自相似方法重复事物的过程，在数学和计算机科学中，指的是在函数定义中使用函数自身的方法。（A调用A）

迭代（iteration）：重复反馈过程的活动，每一次迭代的结果会作为下一次迭代的初始值。（A重复调用B）

递归是一个树结构，从字面可以其理解为重复“递推”和“回归”的过程，当“递推”到达底部时就会开始“回归”，其过程相当于树的深度优先遍历。

迭代是一个环结构，从初始状态开始，每次迭代都遍历这个环，并更新状态，多次迭代直到到达结束状态。

理论上递归和迭代时间复杂度方面是一样的，但实际应用中（函数调用和函数调用堆栈的开销）递归比迭代效率要低。

递归有一个很明显的 “递” 和 “归” 的过程。
递：是将整个问题拆分成子问题的过程
归：是将整个问题拆分到不能再分的时候，将子问题处理后再返回的过程。
迭代更像一个循环的过程。每一次循环都在上一次循环得出的结果上继续运算。

迭代的实现

思路是逐个反转结点之间的指针方向，并把指针pre和curr不断后移

代码如下

public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode current = head;
        while (current != null) {
            ListNode next = current.next;
            current.next = pre;
            pre = current;
            current = next;
        }
        return pre;
    }
1
2
3
4
5
6
7
8
9
10
11

最终结果

递归的实现

首先明确为什么可以用递归。贴出解决该问题的流程图。
满足图中三个条件即可使用递归。另外单链表本身具有一定的递归性质

在递归方法中，必须要明确退出递归的条件。由于递归本身是方法调用自己，因此就可以看作是一个方法的循环。不难想到，这个退出递归的条件也就是递归的基本情形，在方法中写明即可。一般采用if判断语句跳出递归。

public ListNode reverseList(ListNode head) {
        //递归终止条件
        if (head == null || head.next == null) {
            return head;
        }
        //递归中的 递 ————拆分子问题
        ListNode p = reverseList(head.next);
        //递归中的 归 ————解决每个子问题（需要做的事情，做完才能 “归” ）
        head.next.next = head;
        head.next = null;
        return p;
    }
1
2
3
4
5
6
7
8
9
10
11
12

参考资料

递归和迭代解法的讲解视频链接如下。
https://leetcode-cn.com/problems/reverse-linked-list/solution/shi-pin-jiang-jie-die-dai-he-di-gui-hen-hswxy/