一、题目描述

反转链表

给你单链表的头指针 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

二、思路分析

• 本链表反转是一种变形反转，因为之前链表反转是将整个链表进行反转而本题是在链表中部分进行反转。而之前我们在链表反转一种通过两种方式来实现。同样这里也还可以用之前的两种方式【递归】和【指针指向修改】

考点

• 题目就已经暴露了答案了，本题就是考察链表的知识

三、AC 代码&解析

具体逻辑分析

• 在无范围的链表反转中我们只需要考虑交换位置就行了，不需要考虑一个边界的问题，但是本题是将链表中的一部分进行反转这时候我们就需要捕获到这两个边界值。也就是说我们需要开辟两块内存变量存放链表反转范围的起始点(firstNode)和结束点(lastNode)
• 在有效范围内我们进行递归操作实际上是从右侧向左侧开始交换数据。从右侧不断的将右侧的交换数据不断提高，最终会形成如下结构的数据

• 当递归执行结束后，我们只需要将边界的左侧与最新的反转连接进行拼接 。 为什么不需要考虑右侧呢。因为我们是从右侧开始交换的。每次交换都会将最新反转后的节点与右侧进行关联。如上图中2的next指向5

• 在递归结束后我们只需要在left之前的节点与当前保存的firstNode连接即可 ， 及1的next指针指向4

完整动画展示

• 请注意动画播放的比较慢，主要是想让大家看清楚执行的流程。需要动画的可以在站内私信我

具体代码

static class ListNode {
  int val;
  ListNode next;
  ListNode() {}
  ListNode(int val) { this.val = val; }
  ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
private static ListNode firstNode ;
private static ListNode lastNode ;
public ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode pre = new ListNode(-1,head);
    reverseFanwei(pre,head,1, left, right);
    return pre.next;
}

private void reverseFanwei(ListNode pre , ListNode head,int index, int left, int right) {
    if (index == right+1) {
        firstNode = pre;
        lastNode = head;
        return;
    }
    reverseFanwei(head, head.next, index + 1, left, right);
    if (index > left && index <= right) {
        head.next = pre;
        pre.next = lastNode;
    }
    if (index == left) {
        pre.next = firstNode;
    }

}

public static void main(String[] args) {
    ListNode node1 = new ListNode(1);
    ListNode node2 = new ListNode(2);
    ListNode node3 = new ListNode(3);
    ListNode node4 = new ListNode(4);
    ListNode node5 = new ListNode(5);
    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    node4.next = node5;
    D92 leetcode = new D92();
    ListNode resultNode = leetcode.reverseBetween(node1, 2, 4);
    System.out.println(resultNode);
}

• 贴到leetcode上只需要方法部分。该方式是通过递归的方式来实现的。递归的特点就是一直循环下去而我们链表可以理解成从左至右开始执行正好符合我们的思路由右侧开始进行交换数据。和完整反转链表相比我们这里需要在递归结束前记录首位信息并在递归结束后进行首位拼接。

• 结果终于是成功的执行了，但是在成功的道路却不是那么顺利中途还是有很多情况没有考虑清楚的。最终在执行速度上很快，但是内存效率不是很好说明我们还有进步的空间

四、总结

• 本体是leetcode中等水平算法，我已经感觉到明显的吃力了。昨天的数组重复筛选可以从简到繁逐渐优化的过程实现算法，而今天仅仅成功提交就已经耗费大半精力了。
• 算法考察的是逻辑思维及抽象理解能力。实现算法之前要重复理解算法的考点在哪里、实现的方式有哪些、分别有啥优缺点
• 总而言之算法成功通过。下小节我们通过迭代的方式实现范围内链表的反转。这里提前剧透下迭代的方式应该在内存上稍微好点