前言

还有两个月的时间就是金三银四的春招了，我也开始刷算法题了。 在这里给大家推荐一个刷题的入门网站【剑指offer-牛客网】
【剑指offer】这一块儿的题大多数是简单或中等难度的题，很适合刚开始刷题的小伙伴（听说大厂笔试题好多都是里面相同类型的(#^.^#)）。
话不多说，开始讲解链表反转这个问题。
这里我会介绍两种方式，

• 一种是头插法的方式
• 一种是利用双指针来实现 局部反转 到 整体反转的过程

题目链接

【JZ24 反转链表 】

解法一：头插法

讲解代码之前，我想还是先介绍一下尾插法和头插法的区别比较方便大家理解

尾插法

动画：

特点：

添加的节点追加到链表的尾部，遍历单链表时，访问节点的顺序与插入时的顺序相同，如下图所示

头插法

动画：

特点：
添加的节点追加到链表的头部，遍历单链表时，访问节点的顺序与插入时的顺序相反，如下图所示

头插法实现链表反转思路

其实咱们实现链表反转用到的就是 头插法这种 遍历单链表时，访问节点的顺序与插入时的顺序相反的特点

思路：

1. 另外创建一个链表2
2. 遍历初始链表1，然后将链表1里的每个节点以头插法的方式插入到链表2
3. 最终返回链表2

代码实现

import java.util.*;
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        ListNode newHead = new ListNode(0);
        while(head != null) {
            ListNode newNode = new ListNode(head.val);
            // 头插法
            newNode.next = newHead.next;
            newHead.next = newNode;
            
            head = head.next;
        }
        return newHead.next;
    }
}

解法二：双指针 - 局部反转

局部反转实现实链表反转思路

局部反转的意思就是，在遍历单链表的时候就让当前节点指向前一个节点，这样等遍历完整个链表之后 ，整个链表也反转了

如下图：

但是有一个问题：
因为单链表是单向的 ， 就是只有一个next域，那么我们怎样让当前节点指向它的前一个节点呢？
解决方案：
使用双指针，一个指针pre指向前个节点 ， 另一个指针cur指向当前节点

代码实现

public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null;    // 前一个节点
        ListNode cur = head;    // 当前节点 （该引用初始指向head头结点）
        
        while(cur != null) {
            // 1、创建一个新引用指向当前节点的下个节点
            ListNode next = cur.next;
            // 2、当前节点指向上个节点（局部反转）
            cur.next = pre;
            // 3、cur和pre指针后移（先移pre 后移cur，顺序不能反）
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

希望这篇文章对你会有帮助！
如果对于该题你有更好的解题方案，很希望你能把解题思路放在评论区，谢谢！！！