反转链表问题的递归解法

目录

一、反转整个链表

二、反转部分链表

---

一、反转整个链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

 首先在方法中我们需要判断递归终止的情况，如果head==null或者head.next==null，那么我们就可以直接返回head。这不仅仅是递归种植的条件也是当head为空或者head只有一个元素的特殊情况的处理方法。

  然后假设我们已经将递归进行到最后一个元素，即调用一次一次的reverseList(head.next)，使方法中的head变成最后一个结点，然后直接返回最后一个结点。

 然后我们用node来接收刚刚返回的head，并且在接收前就用sec存储当前方法的head.next。

 然后我们让sec.next = head（也就是node.next = head），即调换两者的位置，然后让head.next = null，再返回node到上一次递归。

 这时的我们再继续刚刚的操作。

 一直递归下去，就会得到反转后的链表。返回node即可。

    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode sec = head.next;
        ListNode node = reverseList(head.next);
        sec.next = head;
        head.next = null;
        return node ;
    }

二、反转部分链表

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

 有了反转整个链表之后我们做这道题就简单很多了，首先创建一个count变量，用它来判断是否到达需要反转的位置，如实例一中是从第二个位置开始反转，所以当不满足count>=left&&count<=right条件时，我们只需要让node = head然后，node.next = reverseBetween(head.next,left,right);直接连接上即可。

当满足条件时则进行反转，这个情况下递归的终止条件就变成了left==right，每一次递归都让left+1，最后当left==right时直接返回head即可。

这里有一个特殊情况就是head后面还会有元素，我们不能像之前一样将head.next置为空，设置一个变量successor，初始值为null，让他来存储最后剩余的部分链表，如果没有剩余链表，那么head.next则也是置为空了，如果有连接上即可。

    int count = 0;
    ListNode successor = null;
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(left==right){
            successor = head.next;
            return head;
        }
        count++;
        ListNode node = null;
        if(count>=left&&count<=right){
            ListNode sec = head.next;
            node = reverseBetween(head.next,left+1,right);
            sec.next = head;
            head.next =successor;
        }else{
            node = head;
            node.next = reverseBetween(head.next,left,right);
        }
        return node;
    }