递归：反转链表
各位小伙伴周末愉快呀~又到了周末咯~我们本周来看看一个反转链表的系列题型吧！整体难度从简单到中等，再到困难，完美符合我们的正常刷题过程。come~
首先我们来确定一下listNode的类型结构，对ListNode的定义如下所示：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/反转链表
★LeetCode206 --- 反转链表【简单题】 题目描述 ”
题目描述
1、解题思路
题目要求我们对一个链表中的元素进行对应的反转，并且按照最后的进阶提示，尝试一下递归和迭代两种方法来完成。下面就是这两种方法的解题思路。
迭代法：
对于每一个元素节点cur，我们需要记住该元素的前驱元素pre，以及后驱元素next，然后将cur的下一个链表元素指向前一个链表元素next即可。最终，我们返回最后一个节点，就是新链表的头结点。由此，我们就使用迭代法完成了整个链表的反转。
递归法：
- 我们最终需要返回的是链表的最后一个节点，所以，我们在递归过程中，需要找到最后一个节点，然后将其逐层向上抛出。
- 在每一次递归过程中，我们都需要修改每一个节点的指向，将当前节点
cur的下一个节点next的下一个节点next修改为当前节点。所以此时使用的关系式为cur.next.next=cur - 在修改当前的节点
cur与下一个节点next的指向之后，我们需要对cur的下一个节点指向进行一次新的指定，将其指定为null，再从后向前进行迭代即可。
2、代码实现
//迭代法：
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while(cur != null){
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
} //递归法：
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode last = reverseList(head.next);
head.next.next = head;
head.next = null;
return last;
}反转链表II
★LeetCode92 --- 反转链表II【中等题】 题目描述 ”
题目描述
1、解题思路
这道题只要求我们反转原始链表中从m~n的部分，与我们解决的上一道题有相似之处，在上一道题中，我们是反转整个链表。
当我们反转整个链表时，相当于我们反转链表中从1~length的部分，其中的length为整个链表的长度。
在这道题目中我们可以套用上一题的代码，由于只需要完成m~n的链表，其他部分保持原始顺序。所以，我们可以去寻找链表中第m的元素的位置，然后将第m个元素当做头结点，输入到上一道题目的代码中。在寻找过程中，我们依旧使用递归的方法去探寻，每一次传入的参数将是(head,m-1,n-1)。此时，反转过程中，我们使用到的结束条件就不再是head == null，而是n==1。由此，我们就完成了对上一道题目的改造。
【注意】在我们完成部分链表反转之后，我们还需要将反转后的链表与原始链表连接在一起。这样，我们才可以得到完整的链表集合。
2、代码实现
public ListNode reverseBetween(ListNode head, int m, int n) {
if(m == 1){
return reverseSingle(head,n);
}
ListNode ans = reverseBetween(head.next,m-1,n-1);//记录翻转部分的头结点
head.next = ans;
return head;
}
ListNode next = null;
//从head开始，翻转前n个节点
private ListNode reverseSingle(ListNode head, int n){
if(n == 1) {
next = head.next;
return head;
}
ListNode last = reverseSingle(head.next , n - 1);
head.next.next = head;
head.next = next;
return last;
}反转链表III
★LeetCode25 --- k个一组翻转链表【困难题】 题目描述 ”
题目描述
1、解题思路
这道题又是对上一道题目的升级版本，我们需要按照k的大小作为一组，类似于我们需要反转1~k,k+1~2k,2k+1~3k部分的链表。我们可以结合上一次的代码，按照k的大小进行轮询，当我们确保后面的链表包含有k个节点时，就可以传入当前的头结点，以及k值
2、代码实现
public ListNode reverseKGroup(ListNode head, int k) {
if(k <= 1) return head;//对特殊情况的判断
ListNode a = head;
ListNode phead = head;
for(int i = 0 ; i < k ; i++){//防止剩余链表长度小于k
if(phead == null) return head;
phead = phead.next;
}
ListNode newHead = reverseSingleK(head,k);//翻转一轮链表的k个节点
a.next = reverseKGroup(phead,k);//将每一轮的链表的首尾进行连接
return newHead;
}
//反转前k个链表节点
ListNode end = null;
private ListNode reverseSingleK(ListNode head,int k){
if(k == 1) {
end = head.next;
return head;
}
ListNode last = reverseSingleK(head.next , k - 1);
head.next.next = head;
head.next = end;
return last;
}