问题描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例1:
输入: head = [1,2,3,4,5]
输出: [5,4,3,2,1]
示例2:
输入: head = [1,2]
输出: [2,1]
一、问题分析
这道题常见的解法有两种：双指针迭代 和 递归。
方法一：双指针迭代
1. 申请两个指针，第一个指针叫 prev，最初是指向 null 的。
2. 第二个指针 curr 指向 head，然后不断遍历 curr。
3. 每次迭代到 curr，都将 curr的 next 指向 prev，然后 prev 和 curr 前进一位。
4. 都迭代完了(curr 变成 null 了)，prev 就是最后一个节点了,同时也是新链表的头结点。
接下来一步步分析，首先定义指针：
//定义前置指针
ListNode prev = null;
//定义cur指针
ListNode curr = head;
相应的图解如下：
初始的链表状态：
然后开始移动指针，进行第一次遍历，按照上面分析里的1,2步骤移动后的的结果如下图：
继续移动指针，进行第二次遍历，指针继续按照上面分析里的1,2步骤移动后的的结果如下图：
继续移动指针，进行第三次遍历，指针继续上面分析里的1,2步骤移动后的的结果如下图：
接下来结合代码来看，逐步理解while循环里面代码的具体含义。
二、代码示例
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
//极值判断
if(head == null || head.next ==null){
return head;
}
//定义前置指针
ListNode prev = null;
//定义cur指针
ListNode curr = head;
//开始遍历链表
while (curr != null){
//把当前curr指向的节点的下一个节点暂存起来，用于curr的下一次移动
ListNode next = curr.next;
//把当前curr指向下一个节点，指向prev
curr.next = prev;
//prev指针向前移动一个节点，即指向curr
prev = curr;
//当前curr指向的节点，向前移动一个节点，即指向next
curr = next;
}
//此时对于反转完成的链表，pre来到了链表的头结点，返回即可
return prev;
}
}方法二：递归
使用递归有三个先决条件：
-
大问题可以拆解为N个子问题
-
子问题的求解方式和大问题相同
-
存在最小子问题
反转链表恰好符合这三个条件。我们可以把反转整个链表拆解为反转N个子链表，同时反转子链表与反转整个链表的解题方法相同，存在反转链表节点的最小子问题。
所以我们尝试一下采用递归的思想来解题：
-
使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点ret。
-
每次函数在返回的过程中，让当前结点的下一个结点的 next 指针指向当前节点。
-
同时让当前结点的 next 指针指向 null，从而实现从链表尾部开始的局部反转。
-
当递归函数全部出栈后，链表反转完成。
可以结合下面的图解进行理解。
1.链表未反转之前：
2.递归到链表的最后一个结点，进行反转：
3.继续反转，直到当前节点为null或者当前节点的下一个节点为null，标志着反转结束。
看一下递归的代码。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
//递归找到链表的最后一个节点，并作为反转后的头节点
ListNode ret = reverseList(head.next);
//让当前节点的下一个节点的next指针指向当前节点，也就是进行两个节点之间的指针指向反转
head.next.next = head;
//把当前节点的next指针指向null
head.next = null;
return ret;
}
}总结
反转链表是道很经典的链表题，同时也是链表类型的入门级题目，所以很有必要好好掌握。双指针迭代解法虽然比递归简单些，但是我觉得双指针对理解链表指针的移动很有帮助，值得研究一下。不过两种解法最好都掌握。下篇文章还是反转链表的题型，不过有些难度。
写在最后
本人还维护了微信公众号，里面会持续输入包括但不仅限：算法，计算机网络，MySQL，大数据相关组件等。欢迎踊跃关注，万分感谢！！！
附上二维码：