一、题目描述

找出数组中重复的数字

> 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

二、思路分析

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

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

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

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

当指定范围内数据全部扫描完成之后内部指针结构如上。图中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 &gt;= left &amp;&amp; index &lt;= 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已经被我们记录下来了。下面我们只需要将内部外部指针进行关联就可以了

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 &lt; left; i++) {

        firstNode = firstNode.next;

    }

    ListNode rightNode = firstNode;

    for (int i = 0; i &lt; 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%以上。和我们递归的方式进行对比不难发现。迭代的方式在时间和空间上都是最优的。

四、总结

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

巴特西

说了你可能不信leetcode刷题局部链表反转D92存在bug,你看了就知道了

一、题目描述

二、思路分析

三、AC 代码

bug

添加头结点

四、总结

最新文章

热门文章