当前位置：首页 > article >正文

【递归】 92. 反转链表 II

article 2025/1/24 17:40:28

92. 反转链表 II

解题思路

定义了单链表节点的数据结构，包含整数值 val 和指向下一个节点的引用 next。
在 Solution 类中，定义了一个类变量 successor，用于保存当前节点的后继节点。
实现了 reverseBetween 方法，该方法通过递归实现反转链表中指定范围 [left, right] 的节点。如果 left 等于 1，表示从链表头部开始反转，调用 reverseN 方法。
reverseN 方法用于翻转链表开头的 n 个元素。递归的终止条件是 n 等于 1，此时保存当前节点的后继节点，并返回当前节点。在递归过程中，将链表中的相邻节点反转，确保正确的连接关系。
在 reverseN 方法中，通过递归调用获得新的头节点 last，然后调整相邻节点的指向关系，将当前节点 head 的 next 指针指向 successor，完成反转。
返回反转后的链表的新头节点 last。
总体思路是通过递归实现链表反转，其中 reverseBetween 方法用于处理整个范围的反转，而 reverseN 方法用于处理范围内开头的 n 个元素的反转。通过递归调用和相邻节点的指向关系调整，实现了链表的指定范围反转。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    ListNode successor = null;// 后驱节点

    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;
    }

    // 翻转链表开头的n个元素
    ListNode reverseN(ListNode head,int n){
        if(n == 1){
            successor = head.next;// 保存第 n + 1个节点
            return head;
        }

        ListNode last = reverseN(head.next,n - 1);// 返回新的头节点
        head.next.next = head;// head作为新的尾节点
        head.next = successor;
        return last;
    }
}