leetcode#92.反转链表 II（递归做法）

绝地灬酷狼 2022-11-12 04:24 137阅读 0赞

题目来源：https://leetcode-cn.com/problems/reverse-linked-list-ii/

## 代码 ##

class Solution {
        
        ListNode temp=null;
        ListNode last =null;
    
    	// 这个函数用来处理反转链表的前N个结点
        public ListNode reverseN(ListNode head,int n){
        
            if(n==1){
        
                temp=head.next;
                return head;
            }
            last = reverseN(head.next,n-1);
            head.next.next=head;
            head.next=temp;
            return last;
        }
    
    	// 当left=1时，相当于反转链表的前N个结点
        public ListNode reverseBetween(ListNode head, int left, int right) {
        
            if(left==1){
        
                head = reverseN(head,right);
            }else{
        
            	// 当left!=1时，递归进入reverseBetween
                head.next=reverseBetween(head.next,left-1,right-1);
            }
        return head;
        }
    }

## 总结 ##

这道题要反转从位置 left 到位置 right 的链表节点，可以先写一个`reverseN(ListNode head,int n)`函数用于反转链表的前n个结点，返回反转后的头结点last。

`reverseBetween(ListNode head, int left, int right)`函数中分两种情况：

1.  left=1时：  
    相当于反转链表的前n个结点
2.  left不等于1时：  
    可以转化为left=1时的情况。递归进入`reverseBetween`这个函数，直到进入left=1这个base case就会停止递归。  
    具体就是这行代码：

head.next=reverseBetween(head.next,left-1,right-1);

例如

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

会递归进入`reverseBetween` 反转\[2,3,4,5\]，left=1，right=3，得到\[4,3,2,5\]的头结点4  
此时让原来的头结点1连接上反转后的4就行了  
最后输出\[1,4,3,2,5\]