递归实现链表反转

题：

92. 反转链表 IIlabuladong 题解思路

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

 

示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

 

提示：

• 链表中节点数目为 n
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

 

进阶： 你可以使用一趟扫描完成反转吗？

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode() {}
 7  *     ListNode(int val) { this.val = val; }
 8  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 9  * }
10  */
11 class Solution {
12     ListNode behind=null;
13     public ListNode reverseBetween(ListNode head, int left, int right) {
14         if (left==1) {
15             //如果左边界为1，就是反转前面right个节点
16             return reverseN(head,right);
17         }
18         //否则reverseBetween(head.next,left-1,right-1)为反转后的last节点，将last节点接到当前的head上
19         head.next=reverseBetween(head.next,left-1,right-1);
20         return head;
21     }
22 
23     //反转前N个节点的递归程序
24     public ListNode reverseN(ListNode head,int n){
25         if (n==1) {
26             //behind为后驱节点，就是需要反转的后面那个节点
27             behind = head.next;
28             return head;
29         }
30         //last 是反转的最后一个节点
31         ListNode last=reverseN(head.next,n-1);
32         //将该节点反过来，指向前面的节点
33         head.next.next=head;
34         //头节点需要指向后驱节点
35         head.next=behind;
36         return last;
37     }
38 }