换个思路迭代法解决局部反转问题(发现leetcode一个重大bug)

leetcode重大bug被我发现了，单独执行测试用例通过但是批量跑测试用例是相同的测试用例执行不通过

一、题目描述

======

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

二、思路分析

======

之前我们已经分析过了通过递归的方式解决此问题。递归将问题逐层细化已达到整体问题的解决
而今天我们将从另外一个角度去分析次问题--迭代。所谓迭代就是通过一次循环遍历解决反转问题。而递归不同的是他将是从左至右的方式解决问题
在范围内的链表节点先将他指向一个默认前置节点preNode 。然后将当前节点指针后移在重复next指针指向preNode 。就可以解决问题
这样我们仅仅借助于一个preNode就可以完成节点2的反转。不过这里节点已的next指针还是指向节点2的。这一步我们会在最后处理首尾问题。
最终将会是如下指向问题，对于节点3、节点4也是同样的操作。
当指定范围内数据全部扫描完成之后内部指针结构如上。图中1、2、4、5被特殊标注出来因为这四个分别是外边界和内边界的节点。我们需要特殊将这些边界进行连接。 1指向4 、 2指向5就完成了最终的反转
相信通过上面的动画模拟，你应该可以轻松的理解迭代处理的方式。但是在我们实际处理中边界我们需要特殊存储处理。下面我们就通过代码层面来实现效果

三、AC 代码

=======

bug

按照上面的逻辑，我尝试实现了下

代码语言：java复制

//外边界左侧节点
private static ListNode firstNode ;
//外边界右侧节点
private static ListNode lastNode ;
public ListNode reverseBetween(ListNode head, int left, int right) {
    //preNode 作为接受反转节点
    ListNode preNode=null;
    //用于指向当前操作节点 ，  也是内部右侧节点
    ListNode currentNode = head;
    //存储下一节点，方便赋值
    ListNode nextNode=null;
	//内部左侧节点
    ListNode leftNode=head;
    int index =1 ;
    while (currentNode != null) {
        nextNode = currentNode.next;
        if (index == left-1) {
            //捕获外部边界节点
            firstNode = currentNode;
        }
        if (index >= left && index <= right) {
			//指针修复
            currentNode.next = preNode;
            preNode = currentNode;
        }
        currentNode = nextNode;
        if (index == right) {
            //捕获外部边界节点
            lastNode = nextNode;
            break;
        }
        index  ;
    }
    //因为是指定范围但是有可能是全部链表这时候外部边界都是null
    if (firstNode != null) {
        leftNode = firstNode.next;
        firstNode.next = preNode;
    }
    if (lastNode != null) {
        leftNode.next = lastNode;
        return head;
    } else {
        return preNode;
    }
}

上面这段代码本地运行是成功的。而且在leetcode官网上执行[3,5] ,left=1 , right=1 单独执行输出结果也是[3,5] 时没有问题的。但是当提交执行全部测试用例的时候确保在【3,5】 1 ，1这个测试用例无法通过。我认为是leetcode官网执行测试代码的一个bug

添加头结点

在我们上面代码中虽然leetcode没有通过但是那是leetcode的bug导致的，在里面我们不难发现有很多if else操作。这样的代码很难看至少在代码洁癖面前是不能容忍的。
为什么会有那么的判断，主要是因为我们的外部边界和内部边界可能会出现重合。所以我们在原有的链表中在头部再添加一个默认节点。这样做是为了避免外边界空的情况。
同样是left=2,right=4的情况，我们从红色头结点开始获取到left=2之前的节点和right=4的节点。即node1是我们之前说的firstNode。node5是lastNode。
leftNode=node2;rightNode=node4 。然后我们在将内部链表进行反转。反转的方法就是按照我们上面的逻辑借助另外一个空节点作为preNode。
因为node1,和node5已经被我们记录下来了。下面我们只需要将内部外部指针进行关联就可以了

代码语言：java复制

firstNode.next = rightNode;
leftNode.next = lastNode;

最终将头结点后面部分返回就可以了

代码语言：java复制

private static ListNode firstNode ;
private static ListNode lastNode ;
public ListNode reverseBetween2(ListNode head, int left, int right) {
    ListNode visualNode = new ListNode(-1, head);
    firstNode = visualNode;
    for (int i = 1;i < left; i  ) {
        firstNode = firstNode.next;
    }
    ListNode rightNode = firstNode;
    for (int i = 0; i < right - left   1; i  ) {
        rightNode = rightNode.next;
    }
    ListNode leftNode = firstNode.next;
    lastNode = rightNode.next;
    rightNode.next = null;
    ListNode wpre = null;
    ListNode wcur = leftNode;
    while (wcur != null) {
        ListNode next = wcur.next;
        wcur.next = wpre;
        wpre = wcur;
        wcur = next;
    }
    firstNode.next = rightNode;
    leftNode.next = lastNode;
    return visualNode.next;
}

多执行几次看看最终的效果
速度依旧是那么快，在内存使用上平均值是65%以上。和我们递归的方式进行对比不难发现。迭代的方式在时间和空间上都是最优的。

四、总结

====

迭代和递归是解决链表常用的两种方式。迭代的优点就是不断的循环下去
递归最大的问题就是容易导致死循环，在书写的时候需要特殊注意递归的结束条件

我正在参与2023腾讯技术创作特训营第三期有奖征文，组队打卡瓜分大奖！

2023腾讯·技术创作特训营第三期

0 人点赞

换个思路迭代法解决局部反转问题(发现leetcode一个重大bug)｜Java 刷题打卡