java list顺序反转

大家好，我是图林学院的韩飞，本视频呢给大家讲解这个立的扣子上一道了比较简单的算法题啊，就是这个链表反转，链表反转呢，这个题目的含义啊，就是将单链表的这个链接的顺序把它翻转过来，这里呢提供了一个简单的一个视力， 比如说我们输入一个这样的列表，这个列表呢，呃，元素的话是一到五，那么他的这个顺序的话呢，是从这个根据元素的这个值的这个大小，那从小到大进行的指向，因为我们知道在这个 加法中的这个列表啊，这个漏的节点，对吧？我们列表中的每一个节点就是用漏的来表示，这个漏的中呢有一个 laxt， 那么实际上这个 lax 的就是这个，哎，就这个箭头啊，我们这个箭头呢，一般呢通过这个 lax 的这个属性来进行表示，那 首先呢，我们的这个原始的这个链表呢，它是从小到大进行这个呃这个链接的一个指向的，那我们需要呢就是提供一个函数，然后呢把这个链表呢反转过来啊，那么变成下面这种， 就是呢让这个电表呢变成从大到小进行指向，从大到小啊，按照这大到小的方向进行指向，也就是说把这个方向呢给他翻转过来，这是这道题的一个含义啊， 那么如果，呃在解这道题的时候，一般呢我们面试者呢，其实很容易想到一种解法啊，但是啊，就是如果说这个面试官对这个算法这一块要求会高一点的话，可能呢你想到这种比较简单的算法 的时候，好像他还会继续深入的去问啊，因为针对这道题呢，有两种很经典的算法，那么这两种经典的算法呢，都是我们作为程序员必须要掌握的，那么你如果只回答了其中一种， 另外一种呢，如果回答不上来的话，那么呢其实这道题呢也是有欠缺的。好，那么我们下面呢来看一下这道题啊，针对这道题，他这两种解法啊，分别是什么？ 首先呢我们来呃，这里呢，韩语老师给大家把这几个元素啊已经画在这里了，那么首先我们，呃如果说啊，没有任何思路的话啊，我们呢怎么样来分析这道题？ 我们现在呢是要完成这么一个链表的一个这个链接顺序的一个反转，对吧？那么我们首先呢，它是从小到大进行指向的，我们要把它变成了从大到小进行指向，对不对？从大到小就进行指向。 那么首先我们考虑一个问题啊，这个一，这个元素，我们呢一个元素，一个元素来看，这个元素呢，他通过这个 laxt 这个指针对吧，指向下一个元素，那么如果我们想要反转的话，就说白了就是想让这个 laxt 指向他的上一个元素，对 对，当然我们这里的上一个元素他没有就是闹，对不对？就是指闹，其实想就是想让这个 lax 的指向这个闹，但是呢我们考虑个问题啊，如果说，哎，我拿到第一个元素，拿到第一个元素，我把这个 lax 的指向这个闹的话，那么第二个元素在哪呢？我就找不到了，这个是列表的一个特性 啊，这是列表的特性，列表了，必须根据这个指针呢才能够找到下一个元素。那么如果说我们直接把第一个元素的这个类似的指针改成 not 的话，那么第二个元素就找不到了，所以说我们此时我们就需要一个变量，需要个变量来保存这个指针啊，也就是说 我们在这里呢，哎，再把这个变量给它，呃画出来啊，那么我们在这里呢使用一个 lax 的变量，这个变量呢，我们换一种，呃，换一种颜色啊， 我们使用这个呃灰色代表了这个变量，代表这是这是个变量，对吧？我们使用一个 lax 的变量，也就说我首先我要，我要把这个 lax 的这个指针改成这个 note 之前，对不对？我首先呢要把这个 lax 的呢要把它保存起来， 哎，此时这个类似的实际上他是什么？实际上就是二这个元素，对不对？实际上这个类似的他指向的其实是二这个元素啊，那么此时我就可以相当于呢把这个箭头呢给他断掉了，对不对？断掉了，然后此时这个类似的就指向了一个闹元素，把这个闹给他画出来。 now， 那么此时我们其实就完成了，完成了第一个元素的一个什么，完成了第一个元素的一个翻转，对不对？就是一啊，就指向了他前面。虽然说这个是闹对不对，但是此时我们就完成了第一个元素的一个方 翻转。好，那么接下来第二个元素的翻转，我们再来看一下我们还需要什么？这第二个元素的翻转的时候，首先呢我们就知道了这个类似的变量保存了他自己，对不对？哎，但是这个二的，这个类似的呢？我还要指向前面，对不对？这个类似的我，我需要指向这个类似的，对不对？指向这个一啊， 这里啊，换一下啊，那么我实际上这个二，二的这个 lakes 的，我是希望他能指向这个一的，那么只是我知道这个一是谁吗？也不知道。因为这个一你并没有保存下来，对不对？你并没有保存下来，所以说此时我们还需要一个变量。把这个一了保存下来，那么只是我们需要一个什么变量呢？需要一个 pro 变量 啊，这个 player， 也就是说我的前一个元素是谁？因为正常来说，在我们这个列表里面，每一个元素都只知道他的下一个元素，并不知道他的前一个元素，对不对？ 并不知道他是前一个元素，比如说我四这个变量，我只知道，哎，我这个类似的指向的是五，我知不知道我前一个元素是谁？作为四本身来说，他是不知道的，每一个节点，他只知道他的下一个节点。所以呢，我们如果一啊，我们如果把这个把它断掉了，那么如果，哎，此时 去处理第二个元素的时候，我们会发现呢？我不知道前一个元素是谁，所以说呢，我们还需要了把一啊，把这个前一个元素也得把它保存下来，因此，只是我们又需要一个变量，对吧？需要一个 pro 变量，这个 pro 变量呢，用来保存这个一字几， 那么此时我在便利到二这个节点的时候，我就知道，哎，我可以把这个 player， 对吧？复制给我的这个 lix 的，对不对？那么我这个 lix 的呢，就指向了这个 player 啊，好，那么这是这两个变量，有了这两个变量之后，我们就可以来进行我们的这个，哎，这个解题了，解题怎么 我们来解了，我们来看一下啊，这一道咖啡老师写了一点尾代码，我们通过把这个代码了，把它进行完善啊，把这个上把这个算法呢，哎，把它完善起来，首先呢在这里呢有一个累不累？这个累不累呢？就是一个节点类型啊，一个 listlo 的，就是我们这个列表中的一个节点，那么列表呢有它的值以及到它的一个指针，对吧？然后呢有一个构造器， 那么怎么来写呢？我们首先来看一下啊，我们前面讲了，我们这里呢需要定义两个变量，对不对？一个一个 player 啊，然后还有一个 定义两个变量，在这里定义这两个变量之后，我们呢其实就可以开始了来进行这个叠带，所以说实实际上啊，我们第一种解法也是最容易想到的，就是叠带就是进行变利，对不对？一个元素一个元素处理，一个元素一个元素处理啊，好，那么此时怎么处理呢？ 我们知道要进行这个迭代的话，其实我们在看到这道题的时候，对吧？这个题有多个元素，一个列表，那么肯定此时肯定存在一个循环， 存在一个循环啊，那么这个循环我们到底是使用这个 for 循环，还是使用 yo 循环，对不对？使用这个有限次数循环还是无限次数循环呢？那么在这里其实呢我们并不知道这个链表的一个长度对不对？这个链表的长度我们是不知道的，因为我们在看这个链表里面那些元素啊，它只有它本身的值以及它的 lax 的， 所以我们并不知道它的长度，你不知道它的长度的话，你就不知道这个循环的这个长度有多少，所以在这里呢，我们通常是使用这个 yo 循环，使用 yo 循环啊，当然你也可以使用这个增强负循环， 但是呢，此时我们传入的是一个 list load， 传入的是一个节点啊，一个 hate 的节点， 他只是传入的并不是一个，并不是一个 connection， 因此呢，他并不具有这个迭代器，那么增强后循环他底层是依赖这个迭代器的，我们只是并没有迭代器，所以说增强后循环也是不能用的， 那么我们只能够使用这个，只能使用这个 yo 循环去进行的便利。那么使用 yo 循环的话，那么我们肯定呢，需要有一个这个循环的一个结束条件，对不对？有一个循环结束条件，那么这个循环我们到底结束到？哎？到底循环到什么地方结束了？其实很容易啊，能够想到啊，就是 在我们这个循环中，我们呢其实还需要一个什么？需要一个，需要一个循环变量，对不对？就说我当前到底循环到什么位置了啊？比如说我循环到第一个元素，循环到第二个元素，循环到第三个元素，对不对？那么我当前循环的这个元素是谁？实际上我们还需要一个当前元素，实际上就是什么？就是我们这个货循环中的这 这个 i 对不对？就是负循环中的这个 i 啊，那么只是我们使用使用这个外物循环的话，肯定就没有这个循环变量了，那么此时呢，我们需要自己了来指定这个循环变量，也就是这个 a mist 靠变量啊， 也就是当前变量，那么这个当前变量的话，我们呢传入了一个黑的节点，这个黑的节点实际上传入一个 k 的就意味着你传入了整个链表，对不对？因为这个 k 的里边呢，有这个 lax 的指针来指向了他的下一个节点，我们简单的来看一下这个链表的一个结构啊，那么这个链表的话，我们我在这里呢就是，呃，给他啊 初始化了五个节点，其实这个列表呢，就是通过这五个节点的这个 lax 的指针指向上一个，比如说四指向五对不对？三指向四，二了指向三，一了指向二，那么只是我们如果掉这个方法传入的话，我们只需要了把这个漏的一节点进行传入就可以了，因为这个漏的一节点是 就是 k 的节点，也就说这个列表的第一个节点啊，好，所以说只是这个卡偶元素，对吧？我们就可以把它指定了，指定为这个 k 的， 那么有了这个卡尔这个元素之后，我们其实就可以得到这个循环的一个终止条件是什么呢？因为我们直接将这个 lax 的进行往后，便利的话，我们会发现呢，当你便利到最后一个元素的话，这个 lax 的他指向的是谁啊？ 指向的是闹，对不对？指向的是闹，所以呢，我们在这里就可以确定这个循环变量啊，这个这个这个循环的一个结束条件啊，就这个靠了， 要不等于空，对吧？不等于闹，那么如果说这个靠他要是等于闹的话，直接呢就可以退出这个循环了，好，那么有了这个哎， 确定了这个循环的一个退出条件之后，我们呢就来哎，把我们刚刚的这几个步骤了，把它实现起来就可以了，对不对？首先呢我要把这个类似的这个指针呢，把它保存下来，对不对？ 保存在哪里？保存在这个 lax 的里边啊？保存在这个 lax 里边，那么呢使用这个它点 next， 把它的指针哎保鲜呢，把它的指针保存一下， 保存完指针之后呢，我们就接下来呢就是复制，对不对？也就是说呢把这个 perrave， perrave 啊进行复制，复制给谁了？复制给他的这个 lixt 复制给他啊， 好，只是这个 preray 五了，没有进行初始化啊，我们在这里呢将它置为 note， 因为初始化的时候肯定是一个 note 变量啊， 好，那么完成了这两步操作之后，实际上我们就可以往后了，对不对？就可以往后了，我们相当于了我们要进入下一次循环，但是此时这个靠变量我们还没来得及改，对不对？这个靠变量呢？此时还是 k 的，那么此时我们是不是要将这个 lax 的复制给这个靠，对吧？就是 下一个边上这个 lax 的，其实目前呢来说，它指向的是这个第二个节点啊，指向的是二这个节点，所以说此时我们要把这个一这个节点呢，把这个 lax 的复制为当前节点啊，复制给这个号好。完成了这一步之后， 这里呢我们会发现一个问题，就这个 carl 呢，对吧？它已经有值了，已经呢指向了下一个节点，但是呢我们再去诶去进行这个二这个节点的时候，我们会发现我们二还需要个什么节点？ 需要一个 pro， 此时这个 pro 呢？还没有进行复制，对不对？因为我们把这个 pro 呢复制给了前面的下一个，那么此时这个 pro 我们还需要进行复制啊。 pro 先呢得把这个 cow 复制给这个 pro 啊，把这个 cow 把它保存下来，对不对？就是我们一节点保存在这个 pro 里边，那么此时呢，我们就哎把这个，再把这个类 x 的变成了当前这个元素，然后接着进入下一次循环啊，那么这个其实就是迭代的这个思路，那么最后呢，我们返回这个 pray 五节点就可以了，返回这个 pray 五节点就是我们的这个头节点，对吧？ pray 五节点啊，那么只是这个呃，迭代解决这个列表反转的这个代码其实很简单，就这么几行。 好，我们再来来测试一下，看一下他的这个效果啊，把这个方法呢拿到这个卖方法里面，哎，来执行一下，将这个肉的一节点啊进行传入，然后此时呢他会返回一个 play 五节点啊，我们把这个 play 了，把它获取一下。 好，然后我们在这边呢，呃，通过断点的形式来看吧，因为这个地方打印呢，他会打印一个聚饼啊，我们在这里呢给他一个断点啊，在这里也给一个断点啊，我们来看一下这个呃，两个 节点到底是什么样子的？这个是第一种解法啊，就是通过迭代啊，迭代的方式来解决这个列表反转的一个问题啊， 好，已经进入这里了，我们来先呢来看一下这个漏的一对吧，这个漏的一呢，实际上就是它本身的值是一对不对，然后通过一个 lax 的指针指向二，然后它 lax 的指针呢指向三， 接下来这个类似的指针呢指向四，再类似的呢指向五啊，好，经过我们这个迭代的这个算法之后，我们呢再来看一下好，处理完了之后，我们来看一下这个 pro， 这个 pro 呢，同样的我们把它展开啊， 展开的话的话，第一个节点变成了五啊， next 指向四， next 指向三， next 指向二，再 next 指向一啊，然后再 next 指向闹，因此呢就完成了这个列表的一个反转啊。那么以上呢，就是这 通过迭代的这种形式呢来完成这道算法题，其实呢代码比较简单，对吧？重要的是要理解这个解题的一个啊过程啊，一个思路。那么这边呢，呃， 如果大家啊需要这个代码的，可以呢加一下 up 主的这个 qq 跟微信啊，以及呢这个解题的思路都有来写在这里，然后最后呢还有这个，呃，原代码都贴在这里啊，包括我们啊，后面还会讲到使用第二种解法，也就是这个地规的这个思路来解决啊，怎么了怎么样呢来解决这道算法题。 那以上呢就是第一个解法啊，就是通过迭代的方式来解决这个列表啊反转的这个问题。

上面的话呢，我们实际上来说已经对这个单单个元素集合的接口特点做了一些解读了啊，比如说像我们的 clink 接口，像我们的 list 接口，像我们的赛接口，其实啊像这些接口有什么东西我们应该怎么看呢？ 那实际上来说，如果是第一次接触到了他的话呢，应该是看他的 apn 档还记得吧？ apn 档啊，所以这时候的话，大家伙可以跟着我来看一眼，在这一头我们可以到 ida 里面来看，也可以，或者在我们的这个 apn 档里面去看也可以，都可以啊，好，搜，搜索一下，大家伙可以看到了这个东西数在哪个包呢？在这个抓 uto 里面的包里面啊。来，咱们回车。 好，进来之后大家会看到这个东西呢，是一个接口，在这接口里面呢，后面跟了一个小东西，这个小东西以前没见过对不对？哎，好，简单说一下，这个东西呢是要泛行，所以泛行又是什么？就未来我这边存的操作什么类型，我可以通过这个东西来确定。啥意思呢？举个例子说这是个接口，那我们后面跟上这个 e 这一呢，我可以传具体的东西，比如传的是一个字符串，那意味着什么？意味着集合放东西就是字符串类型啊，就这意思啊。好，具体的话我们用的时候再来说一下。那接着我们先来看一下这里面的话呢，下面我们可以看到这边有相关性的一些方法，然后呢我们要左侧有一条结构，再看一眼来看看， 你看啊，这里面有什么方法呢？咱们可以看一眼，首先的话呢，这些东西是包含，这是转换成数组，对吧？就是我们的集合跟这个数组之间是可以交换的，看到没有？可以转换数组，看到没啊？转换数组，然后呢？这是做一个增加，是吧？爱了，做一个增加，这是吕目做一个删除，这个呢是看我们有没有包含一个集合，集合有没有包含集合，对不对？ 哎，然后这个是增加一个大集合，看到吗？哎，增加个大集合，然后这是移除，等等啊， ok， 我们看到这么多啊，这么多东西好，好了，所以我们看到这边基本上来说的话，整体的一个结果来说啊，就是我们这里面可以干嘛可以做增加 删除啊，直接删除这些基本的操作， ok 啊，好，然后大家可以判断啊，判断他是否存在，对吧？判断他是否存在啊，大致呢就是这么些逻辑了啊，好，这是整体的一个情况，然后还可以做一个便利，你看这有个叠带器啊，这东西是来便利的啊， 好，这，这是整个 cleat 接口定义的一些基本性的方法，我们看到有增加删除，然后查询呢，就是判断他里面在不在里面的意思啊，然后呢是便利，好， ok， 这是这个东西的定义，同理呢，我们还有看到下面的孩子接口叫 lis 接口，这个 lis 接口这里面的话呢，他呢有个特点叫做他规定是有序的，我们给他看一眼啊，就是他的 lis 接口， 同理，我们可以掐一敲一下，然后敲一个 list 啊， list 这边的话呢，现在我们看到既然这边的话有我们常规的名称，我们叫 jay util 啊，点 list 好，点过来。好，在这个接口这里面的话呢，我们也可以看一下左侧的结构，然后看看里面有什么相关性的方法。 呃，这一头我们可以看一下啊，在这边呢，注意一个点，除了上面这常规性的方法，比如说包含就是查询他在不在里面，是吧？然后迭代，就是说我们去便利的啊，便利展示数据的，然后添加删除这些方法跟我们什么很明显的看到这里面啊，注意看 这些东西啊，很显然是继承着什么呢？继承着我们他的副接口的遗产，对不对？你看都是 collection 里面的，看到没有副接口的遗产都继承过来了，然后再往下看，大家可以看到这些什么，这是他自己后代经过自己的努力发展的，你会看到什么？这里面有个东西叫 get， 他给了一个什么？给了一个 index， 那很显然 index 是什么？是不是缩影啊？就第几个？第几个，所以这里头很显然这个历史里面的话呢，他就有了一个什么，有了个顺序性，就是我可以拿到第几个元素的意思。哎，这增加了一个什么顺序性的这么一个特点，看懂了吧？哎， ok， 这是 list 啊，这 list。 好，那么再再往后看，我们再看一下什么，看下这个 set 啊，看 set， 再看，然后去找找，我们找 util 里面的这个 set， 这个类回车。好，这个地方的话呢，我们来看一眼，你会看到这里面压根就没有刚才那个什么 index， 没有吧？哎，首先前面这一堆不用看了，都是继承着 collection 的 啊，开始选的好，那么在这边的话呢，实际上来说，我们看到目前为止看不出有什么特别东西，那在这边的话呢实质上啊他这个地方我们可以看一下啊这个 set 啊 set 往上看一眼 这个地方的话呢他是让来说他会去做什么。做一个你看一眼 a collection 来这样吧把这东西拿过来啊拿过来复制一下 然后呢把它拿过来。哎这样我们就来看一下因为大家的英文能力都差不多你看不包含重复元素的集合是不是一目了然对吧所以的话呢你看我们其实给大家一些结论都来自哪来自于这些文档 里面讲东西懂我意思吧。哎只是说呢这个时候其实东西很明白的摆这里啊就摆这里了看懂 ok 所以上面这写的这些内容实际上来说都是什么都是从那边拿过来的啊。好 ok 好了啊那所以的话现在清晰了我们看刚刚刚才来才回忆一下啊你会看到这个接口里面定好的一些方法是吧是有限的啊。 然后呢这个地方的话增加了什么？增加了他的 index 所以是不是所以他是有序的啊所以有序什么是顺序元素的存入顺序和读取的顺序是一致啊不要跟排序搞混了啊。好然后的话呢 set 接口是什么他没有新增方法 很明显没有对不对但他内部希望保证什么不包含重复元素因为刚才我们看到这里面整个 set 里面你看到好像这家伙啥东西发展就纯靠什么叫叫叫什么叫什么。呃就啃老是吧。纯啃老啊纯啃老 时尚来说的话他也是有理想的啊他也是有理想的你看到这样的话呢他是有干嘛？他有想法的啊？他有想法的，看到没有？哎， ok， 好了啊，那整体的设计就是这样子设计了，所以呢，我们通过代码的方式呢，可以更清晰的看到这接口的东西。 ok， 这个地方的话讲这个视频啊，重点是要干嘛？是想让你掌握这种方式，懂我意思吧？掌握这种方式，这种方式掌握了才更关键，好吧？ ok 啊，这是我们想给大家传递的东西啊。 好了，把这个技能掌握了，这样的话呢，后续如果你想再学习说。哎，老师呢，这里面是不是还有其他的实现类啊？他有什么特点呢？哎，同学们，这个技能你掌握了之后，你是不是应该自己可以去看一看， 对不对啊？你自己看一看是不是就 ok 了？好了，所以呢，我们要的是找一种方法，而不是说把所有的技术都一到一百全部给你讲一遍，这个没有意义，因为未来还有一百零一到两百，两百零一到三百，那怎么办？ 那不就完蛋了吗？所以的话，我要掌握的是什么？是用学技术的方式，这才是关键点啊。好，那就说到这。