【链表】为什么做了很多链表的算法题，还觉得自己不会链表
建议大家的阅读方式
- 首先思考下自己认识的链表
- 对比下你认识的链表和我梳理的链表有什么不同，如果是我梳理的有疑问或者不详尽，欢迎评论区讨论
- 在思考下哪里自己有疑惑，疑惑是什么
- 对比下我梳理的实际困惑点和新的认识（这里先给出了答案），看下是否你也有困惑，认识不清晰的
- 就困惑的点看下我梳理的实验部分，看是否回答了你的问题，如果没有，欢迎评论区告诉我，我们一起进步
- 如果你对链表已经很熟悉了，那欢迎你看下算法中的巧劲部分，后续我会持续更新，也欢迎你在评论区中指正或者告诉我其他你希望看到的内容
- 最后思考下，关于链表，还有哪些是你的困惑，希望我补充的内容，也欢迎评论区告诉我
- ���后的最后，希望大家读完了这篇文章，思考下自己是否有提升，提升了什么？希望大家和我一起，每天进步一点点。
困扰
- 我到底会不会链表
- 为什么做了很多链表的算法题，还觉得自己不会链表
- 为什么一会觉得自己会了，一会有觉得自己不会了呢？
关于困惑的思考
算法题中自己的实现方式
- 只是按照业务的角度/算法case的角度去实现这个业务
- 算法题做完了，感觉懂了链表，又好像没懂
- 到底是引用了之前的实例，还是new了一个新的实例，每次都是靠尝试
决定仔细梳理下自己关于链表的认识
所以我做了下面的几件事
- 梳理下当前我认为的链表
- 梳理了下做过算法题中的一些巧劲（后续持续更新）
- 梳理了下困惑我的点
- 梳理了下具体会产生困惑的case
- 通过代码debug实验每个具体case的结果
- 通过结果将答案卸载了困惑case后面
什么是链表
这一刻我的认识
- 链表是一种存储结构
- 可分为
- 单向链表
- 链表的结构中，有一个当前元素的业务值，还有下一个元素实例的引用（下一个元素的地址）
- 双向链表
- 链表的结构中，有一个当前元素的业务值，下一个元素的实例的引用（下一个元素的地址），上一个元素实例的引用（上一个元素的地址）
- 循环链表
- 在一个 **循环链表**中, 首节点和末节点被连接在一起
- 在单向链表、双向链表中均可实现
- 单向链表
- 可分为
- 遍历链表时，只能由第一个元素，一个一个的遍历到最后一个元素
链表算法中的巧劲（待后续持续更新）
- 双链表元素移动
- 将链表赋值给多个变量
- 通过不同的步长，找到链表的中间元素
- 适用于回文数以及需要找到链表中间元素的场景
- eg：例如链表a->b->c->b->a
- 将链表赋值给两个变量m,n
- 遍历链表m和n，m的遍历步长为2，n的遍历步长为1，
- 判断步长长的链表的下一个元素（链表长度为奇数）、下下个元素是否为空（链表长度为偶数），如果为空即为本次遍历结束
- 当链表m遍历结束时，链表n当前元素的引用，即为中间元素c的实例
- 具体过程：
- 第一步过后，链表m的变量引用元素c的实例，链表n的变量引用元素b的实例
- 第二部过后，链表m的变量引用元素a（第二个）的实例，链表n的变量引用元素c的实例
- 由于链表m的下一个元素为空，即为遍历结束，此时链表n引用的元素是c的实例
- 返回链表第k个元素
- 给两个变量赋值链表，a,b
- 先将第一个链表a移动k次
- 再同时移动两个链表，当链表a移动到达链表结尾时，链表b当前的元素即为链表的第k个元素
- 判断两个链表是否相交
- a链表元素向后移动，当移动到最后一个元素时，将b链表的表头元素赋值给链表a
- b链表元素向后移动，当移动到最后一个元素时，将a链表的表头元素赋值给b链表
- 判断a,b两个链表是否相交，如果有相交节点，会相遇，否则两个链表无相交节点
- ps：假设a链表距离相交节点c之前长度为m，b链表距离相交节点c之前距离长度为n，相交链表以c元素开头长度为k，按照上述流程，则a链表遍历的过程为m+k+n, b链表遍历过程为n+k+m，会在此时引用相同元素的实例
- 特例1，当m=n时，会直接在m/n时引用节点c的实例
- 特例2，当两个链表没有相交是，在整个m+k+n/n+k+m的过程中不会引用相同节点
实际的困惑点
- 没有分清链表中的变量引用与实例
- 造成了不知道什么情况下修改一个变量引用的链表会影响另一个变量引用的链表
- 是只移动元素，还是在移动元素的时候，修改了某个node的next元素对应的实例
- 通过while遍历链表时，只是移动了元素，没有做赋值
- 在遍历的同时，需要删除某个元素，改变了之前链表的结构
- 如果要保留原来的链表，需要在遍历的同时复制出一个结构相同的链表
- 如果只是想要改变后的链表，那可以返回一个引用原链表头元素的变量，即返回链表头元素的实例
- 如果要移动链表的某个元素
- 注意在遍历时，注意正在遍历的node，不要讲已经遍历完的元素的实例赋值给node元素的next引用，否则会死循环
新的认识（模糊的点做了试验后）
- 将一个链表sourceNode赋值给一个新的变量temp时，这时sourceNode和temp引用同一个实例
- 通过sourceNode遍历整个链表之后，null被赋值给了sourceNode，temp还是引用之前的实例
- 链表结构中，每new一个新的元素时，会实例化一个链表的node
- 当遍历/变量赋值时，如果已有node的实例，当前实例赋值给变量
- 使用while遍历链表时，会将链表中元素的实例逐步的赋值给链表变量，不会建立新的实例
- 在分析空间复杂度的时候，之前会疑惑的点
- 一个链表是由一个一个的实例组成的，每一个链表node都是一个实例，通过变量的赋值，只是将变量引用了该实例
- 两个链表引用同一个链表元素node，且两个链表中的元素是相同的，这时其实只有一个链表的实例，所以在改变一个链表的元素结构时，另一个链表元素也发生了变化。
- 本质上虽然有两个链表的变量，但引用的是同一个链表的实例，所以当通过其中一个链表变量，改变整个链表时，另一个变量引用的链表也发生了变化
- 所以在使用链表时，首先要区分是需要一个引用原链表的变量，还是需要一个结构完全相同，但不同实例的链表，这样就不会发生通过修改一个链表，影响另一个链表的问题了
- 如何实现？请大家自己思考下~
- Java世界只有值传递，通过赋值的方式，引用实例
模糊的点
-
new 了一个ListNode temp 赋值当前的链表（ListNode temp = head），temp只是一个变量？还是和head完全相等
- #是同一个实例！！
做测试
@Test public void isTheSame() { ListNode sourceNode = new ListNode(4); sourceNode.next = new ListNode(5); sourceNode.next.next = new ListNode(1); sourceNode.next.next.next = new ListNode(9); ListNode temp = sourceNode; assertThat(sourceNode).isEqualTo(temp); } public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } --- idea快捷键默认inline后 @Test public void isTheSame() { ListNode sourceNode = new ListNode(4); sourceNode.next = new ListNode(5); sourceNode.next.next = new ListNode(1); sourceNode.next.next.next = new ListNode(9); assertThat(sourceNode).isEqualTo(sourceNode); } --- debug后，查看两个实体完全是一个实例-
- 用sourceNode做遍历之后temp和sourceNode有什么变化
- - temp还是原来的链表？#temp还是原来的链表
- - sourceNode只是链表的最后一个元素？#sourceNode是null
做测试
@Test public void isTheSame() { ListNode sourceNode = new ListNode(4); sourceNode.next = new ListNode(5); sourceNode.next.next = new ListNode(1); sourceNode.next.next.next = new ListNode(9); ListNode temp = sourceNode; while(null != sourceNode){ System.out.println(sourceNode.val); sourceNode = sourceNode.next; } assertThat(sourceNode).isEqualTo(temp); } --- sourceNode变为null --- debug看：sourceNode是null，temp还是原来的实例835-
如果用相同的方式new 两个链表出来，他们是引用了同一个实例的么？
- 他们是两个实例
- 链表中的node也是不同的实例
实验
@Test public void isTheSame() { ListNode sourceNode = new ListNode(4); sourceNode.next = new ListNode(5); sourceNode.next.next = new ListNode(1); sourceNode.next.next.next = new ListNode(9); ListNode temp = new ListNode(4); temp.next = new ListNode(5); temp.next.next = new ListNode(1); temp.next.next.next = new ListNode(9); assertThat(sourceNode).isEqualTo(temp); } --- 首先他们不是同一个实例 --- debug看他们是两个实例 --- 他们里面的链表node也是不同的实例-
如果使用相同的链表node，两个链表会使一个实例么？
- 他们是不同的实例
实验
@Test public void isTheSame() { ListNode five = new ListNode(5); ListNode one = new ListNode(1); ListNode nine = new ListNode(9); ListNode sourceNode = new ListNode(4); sourceNode.next = five; sourceNode.next.next = one; sourceNode.next.next.next = nine; ListNode temp = new ListNode(4); temp.next = five; temp.next.next = one; temp.next.next.next = nine; assertThat(sourceNode).isEqualTo(temp); } --- 他们是两个实例 --- 链表中的node是相同的实例-
使用两个变量sourceNode和temp，使用已有node构建两个链表，会是同一个链表么？
- 他们是同一个实例，与链表node ： four是同一个实例
实验
@Test public void isTheSame() { ListNode four = new ListNode(4); ListNode five = new ListNode(5); ListNode one = new ListNode(1); ListNode nine = new ListNode(9); ListNode sourceNode = four; sourceNode.next = five; sourceNode.next.next = one; sourceNode.next.next.next = nine; ListNode temp = four; temp.next = five; temp.next.next = one; temp.next.next.next = nine; assertThat(sourceNode).isEqualTo(temp); } --- 他们是同一个实例 --- 他们和链表node four是同一个实例-
在上面的基础上，遍历sourceNode，每一步之后的实例，与链表node元素是同一个实例么？
- 是的
实验
@Test public void isTheSame() { ListNode four = new ListNode(4); ListNode five = new ListNode(5); ListNode one = new ListNode(1); ListNode nine = new ListNode(9); ListNode sourceNode = four; sourceNode.next = five; sourceNode.next.next = one; sourceNode.next.next.next = nine; ListNode temp = four; temp.next = five; temp.next.next = one; temp.next.next.next = nine; while(null != sourceNode){ System.out.println(sourceNode.val); sourceNode = sourceNode.next; } assertThat(sourceNode).isEqualTo(temp); } --- 每遍历一步，是将链表下一个node的实例赋值给当前变量起始
遍历第一步之后
- 两个变量引用同一个实例，当一起一个链表元素有变动，那变动的链表，会生成一个新的实例么？
- 不会，且两个链表的元素都变了
实验
@Test public void isTheSame() { ListNode four = new ListNode(4); ListNode five = new ListNode(5); ListNode one = new ListNode(1); ListNode nine = new ListNode(9); ListNode sourceNode = four; sourceNode.next = five; sourceNode.next.next = one; sourceNode.next.next.next = nine; ListNode temp = four; temp.next = five; temp.next.next = one; temp.next.next.next = nine; //改变链表元素 temp.next = temp.next.next; assertThat(sourceNode).isEqualTo(temp); } --- 在改变链表元素之前，两个链表引用了同一个元素的实例 --- 在改变之后，两个链表还是引用了four这个节点的实例 --- 在改变之后，两个链表的元素都变了改变链表之后
-
移动链表中的某个元素
- eg:将 4→5→1→9变成4→1→5→9
移动过程
beginning temp = 4, temp.next = 5 temp1 = 5, temp1.next = 1 temp2 = 1, temp2.next = 9 temp3 = 9, temp3.next = null change temp.next to 1 use: temp.next = temp2 so temp = 4, temp.next = **1** temp1 = 5, temp1.next = 1 temp2 = 1, temp2.next = 9 temp3=9, temp3.next = null change temp1.next to 9 use : temp1.next = temp3 so temp = 4, temp.next = 1 temp1 = 5, temp1.next = **9** temp2 = 1, temp2.next = 9 temp3=9, temp3.next = null change temp2.next to 5 use : temp2.next = temp1 so temp = 4, temp.next = 1 temp1 = 5, temp1.next = 9 temp2 = 1, temp2.next = **5** temp3=9, temp3.next = null
代码
public ListNode changeList(ListNode source, int changePoint) { ListNode temp = source; while (null != temp) { if (changePoint == temp.next.val) { ListNode temp1 = temp.next; ListNode temp2 = temp.next.next; ListNode temp3 = temp.next.next.next; temp.next = temp2; temp1.next = temp3; temp2.next = temp1; break; } temp = temp.next; } return source; } @Test public void isTheSame() { ListNode sourceNode = new ListNode(4); sourceNode.next = new ListNode(5); sourceNode.next.next = new ListNode(1); sourceNode.next.next.next = new ListNode(9); ListNode target = new ListNode(4); target.next = new ListNode(1); target.next.next = new ListNode(5); target.next.next.next = new ListNode(9); ListNode temp = changeList(sourceNode, 5); while (null != temp) { System.out.println(temp.val); temp = temp.next; } }~end~
-
-
- 双链表元素移动
- 链表是一种存储结构
The End