1. 递归反转整个链表

这也是力扣第 206 题「反转链表」，递归反转单链表的算法可能很多读者都听说过，这里详细介绍一下，直接看代码实现：

// 定义：输入一个单链表头结点，将该链表反转，返回新的头结点
ListNode reverse(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode last = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return last;
}
 

递归魔法：反转单链表 | labuladong 的算法笔记

看起来是不是感觉不知所云，完全不能理解这样为什么能够反转链表？这就对了，这个算法常常拿来显示递归的巧妙和优美，我们下面来详细解释一下这段代码。

对于递归算法，最重要的就是明确递归函数的定义。具体来说，我们的 reverse 函数定义是这样的：

输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点。

明白了函数的定义，再来看这个问题。比如说我们想反转这个链表

那么输入 reverse(head) 后，会在这里进行递归：

ListNode last = reverse(head.next);

不要跳进递归（你的脑袋能压几个栈呀？），而是要根据刚才的函数定义，来弄清楚这段代码会产生什么结果：

这个 reverse(head.next) 执行完成后，整个链表就成了这样：

看这里; 链表反转(递归法)_哔哩哔哩_bilibili

并且根据函数定义，reverse 函数会返回反转之后的头结点，我们用变量 last 接收了。

现在再来看下面的代码：

head.next.next = head;

head.next = null;
return last;

神不神奇，这样整个链表就反转过来了！递归代码就是这么简洁优雅，不过其中有两个地方需要注意：

1、递归函数要有 base case，也就是这句：

if (head == null || head.next == null) {
    return head;
}

意思是如果链表为空或者只有一个节点的时候，反转结果就是它自己，直接返回即可。

2、当链表递归反转之后，新的头结点是 last，而之前的 head 变成了最后一个节点，别忘了链表的末尾要指向 null：

head.next = null;

理解了这两点后，我们就可以进一步深入了，接下来的问题其实都是在这个算法上的扩展

双指针解法

//双指针法，画个图很好理解
class Solution{
	public ListNode reverseList(ListNode head){
		ListNode pre = null;
		ListNode cur = head;
		ListNode temp = null;
		while(cur != null){
			temp = cur.next;
			cur.next = pre;
			pre = cur;
			cur = temp;
		}
		return pre;//返回pre是因为cur指向null的时候，pre正好指向为头结点
	}
}
 

public ListNode ReverseList (ListNode head) {
 
        // write code here
 
        //双指针解法
 
        // ListNode cur = head;
 
        // ListNode pre = null;
 
        // ListNode temp = null;
 
        // while(cur!=null){
 
        //     temp = cur.next;
 
        //     cur.next = pre;
 
        //     pre = cur;
 
        //     cur = temp;
 
        // }
 
        // return pre;
 
  
 
        //双指针到递归解法
 
        return  Reverse(head,null);
 
    }
 
  
 
    public ListNode Reverse(ListNode cur,ListNode pre){
 
        if(cur == null){
 
            return pre;
 
        }
 
  
 
        ListNode temp = null;
 
        temp = cur.next;
 
        cur.next = pre;
 
       //接下来移动指针即可
 
       return  Reverse(temp,cur);
 
    }