递归法

在遍历链表时，使用的都是相同操作来操作链表的不同部分，此时可以采用递归法。

在双指针法（🔗）中的反转链表，两两交换链表中的节点都可以使用递归法，以两题为例：

反转链表

递归方法一：
递归法相对抽象一些，但是其实和双指针法是一样的逻辑，同样是当cur为空的时候循环结束，不断将cur指向pre的过程。
关键是初始化的地方，可能有的同学会不理解， 可以看到双指针法中初始化 cur = head，pre = NULL，在递归法中可以从如下代码看出初始化的逻辑也是一样的，只不过写法变了。

   class Solution {
        /**
         * 递归法（从前向后）
         *
         * @param head
         * @return
         */
        public ListNode reverseList(ListNode head) {
            return reverse(null, head);
        }
        private ListNode reverse(ListNode pre, ListNode cur) {
            // 当cur为空时停止递归
            if (cur == null) {
                return pre;
            }
            // 保存下一个节点
            ListNode tmp = cur.next;
            // 转换指针指向
            cur.next = pre;
            // 继续调用递归
            return reverse(cur, tmp);
        }
   }

递归方法二：

// 从后向前递归
class Solution {
    ListNode reverseList(ListNode head) {
        // 边缘条件判断
        if(head == null) return null;
        if (head.next == null) return head;
        // 递归调用，翻转第二个节点开始往后的链表
        ListNode last = reverseList(head.next);
        // 翻转头节点与第二个节点的指向
        head.next.next = head;
        // 此时的 head 节点为尾节点，next 需要指向 NULL
        head.next = null;
        return last;
    } 
}

两两交换链表中的节点

递归法

    class Solution {
        /**
         * 递归法（从右到左）
         *
         * @param head
         * @return
         */
        public ListNode swapPairs(ListNode head) {
            // 递归结束的条件
            if (head == null || head.next == null) {
                return head;
            }
            // 获取头结点的下一个节点
            ListNode nextNode = head.next;
            // 调用递归进行循环
            ListNode newNode = swapPairs(nextNode.next);
            // 转换指针指向
            nextNode.next = head;
            head.next = newNode;
            // 返回nextNode用来连接上一个节点
            return nextNode;
        }
    }

92. 反转链表 II

递归法

https://labuladong.github.io/algo/2/18/18/

public ListNode reverseBetween(ListNode head, int left, int right) {
    if (left == 1) {
        return reverseN(head, right);
    }
    head.next = reverseBetween(head.next, left - 1, right - 1);
    return head;
}
ListNode successor = null;
public ListNode reverseN(ListNode node, int n) {
    if (n == 1) {
        // 停止递归，并记录下一个节点
        successor = node.next;
        // 反转本身
        return node;
    }
    ListNode last = reverseN(node.next, n - 1);
    node.next.next = node;
    node.next = successor;
    return last;
}

迭代法

https://leetcode.cn/problems/reverse-linked-list-ii/solution/fan-zhuan-lian-biao-ii-by-leetcode-solut-teyq/
迭代法思路不难，就是找到中间的链表，置null后，单独反转后在连接。

public ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode pre = dummy;
    // 找到开始交换链表的前一个节点
    for (int i = 0; i < left - 1; i++) {
        pre = pre.next;
    }
    ListNode rightNode = pre;
    for (int i = 0; i < right - left + 1; i++) {
        rightNode = rightNode.next;
    }
    ListNode succ = rightNode.next;
    ListNode leftNode = pre.next;
    // 注意置为null，再反转
    rightNode.next = null;
    pre.next = null;
    // 第 4 步：同第 206 题，反转链表的子区间
    reverse(leftNode);
    pre.next = rightNode;
    leftNode.next = succ;
    return dummy.next;
}
public void reverse(ListNode head) {
    ListNode cur = head, pre = null;
    while (cur != null) {
        ListNode temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
}