logo头像

学如逆水行舟,不进则退!!!

文章目录

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

一、题目描述

链表反转

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

二、思路分析

  • 之前我们已经分析过了通过递归的方式解决此问题 。 递归将问题逐层细化已达到整体问题的解决

image-20210520092044810

  • 而今天我们将从另外一个角度去分析次问题–迭代。所谓迭代就是通过一次循环遍历解决反转问题。而递归不同的是他将是从左至右的方式解决问题
  • 在范围内的链表节点先将他指向一个默认前置节点preNode 。然后将当前节点指针后移在重复next指针指向preNode 。就可以解决问题

  • 这样我们仅仅借助于一个preNode就可以完成节点2的反转。不过这里节点已的next指针还是指向节点2的。这一步我们会在最后处理首尾问题。

image-20210520101924193

  • 最终将会是如下指向问题,对于节点3、节点4也是同样的操作。

image-20210520102153449

  • 当指定范围内数据全部扫描完成之后内部指针结构如上。图中1、2、4、5被特殊标注出来因为这四个分别是外边界和内边界的节点。我们需要特殊将这些边界进行连接 。 1指向4 、 2指向5就完成了最终的反转

  • 相信通过上面的动画模拟,你应该可以轻松的理解迭代处理的方式。但是在我们实际处理中边界我们需要特殊存储处理。下面我们就通过代码层面来实现效果

三、AC 代码

bug

  • 按照上面的逻辑,我尝试实现了下
//外边界左侧节点
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

image-20210520104258995

添加头结点

  • 在我们上面代码中虽然leetcode没有通过但是那是leetcode的bug导致的,在里面我们不难发现有很多if else操作。这样的代码很难看至少在代码洁癖面前是不能容忍的。
  • 为什么会有那么的判断,主要是因为我们的外部边界和内部边界可能会出现重合。所以我们在原有的链表中在头部再添加一个默认节点。这样做是为了避免外边界空的情况。

image-20210520132414970

  • 同样是left=2,right=4的情况,我们从红色头结点开始获取到left=2之前的节点和right=4的节点 。 即node1是我们之前说的firstNode。node5是lastNode。
  • leftNode=node2;rightNode=node4 。然后我们在将内部链表进行反转。反转的方法就是按照我们上面的逻辑借助另外一个空节点作为preNode。

image-20210520135606544

  • 因为node1,和node5已经被我们记录下来了。下面我们只需要将内部外部指针进行关联就可以了
firstNode.next = rightNode;
leftNode.next = lastNode;
  • 最终将头结点后面部分返回就可以了
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;
}
  • 多执行几次看看最终的效果

image-20210520135905591

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

四、总结

  • 迭代和递归是解决链表常用的两种方式。迭代的优点就是不断的循环下去
  • 递归最大的问题就是容易导致死循环,在书写的时候需要特殊注意递归的结束条件
上一篇
坚持原创技术分享,您的支持将鼓励我继续创作!

评论系统未开启,无法评论!