刷了LeetCode的链表专题，我发现了一个秘密！

{"type":"doc","content":[{"type":"heading","attrs":{"align":null,"level":1},"content":[{"type":"text","text":"刷了LeetCode的链表专题，我发现了一个秘密！"}]},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"引言"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"codeinline","content":[{"type":"text","text":"链表"}]},{"type":"text","text":"是以节点（node）存储的"},{"type":"codeinline","content":[{"type":"text","text":"链式存储结构"}]},{"type":"text","text":"，一个node包含一个data域（存放数据）和一个next域（存放下一个node的指针），链表的各个节点不一定是连续的，它可以分为"},{"type":"codeinline","content":[{"type":"text","text":"带头结点"}]},{"type":"text","text":"和"},{"type":"codeinline","content":[{"type":"text","text":"不带头结点"}]},{"type":"text","text":"。头结点仅包含next域。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/58/58ef4b3ce735eb6a8db02a6b51153f35.png","alt":"image-20201103222213252","title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"如果不熟悉链表的同学，"},{"type":"link","attrs":{"href":"https://mp.weixin.qq.com/s/BOPP8JpDWNCqUfK8_SZtoA","title":""},"content":[{"type":"text","text":"建议先看看我的一篇文章"}]},{"type":"text","text":"。在这篇文章中，主要讲解使用链表的小技巧，如何使用这些技巧来解题，深入解析了"},{"type":"codeinline","content":[{"type":"text","text":"LeetCode"}]},{"type":"text","text":"中具有"},{"type":"codeinline","content":[{"type":"text","text":"代表性"}]},{"type":"text","text":"的链表题目，相信我，看了这篇文章，你再也不用担心关于链表的题目了。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"1、链表的几个概念讲解"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"事实上，链表的结构比较简单，阻碍我们理解链表的常常是因为链表的"},{"type":"codeinline","content":[{"type":"text","text":"指针"}]},{"type":"text","text":"、"},{"type":"codeinline","content":[{"type":"text","text":"边界问题"}]},{"type":"text","text":"等，这有时会让我们很烦躁，不要慌，我们下面一一对这下概念解析，相信你看了会有收获。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":3},"content":[{"type":"text","text":"1.1链表中的的指针是什么"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"我们学习C语言时，学过指针，它描述的是指向一个"},{"type":"codeinline","content":[{"type":"text","text":"内存地址"}]},{"type":"text","text":"，在Java语言中，是不存在指针的，但是我们可以把它理解为"},{"type":"codeinline","content":[{"type":"text","text":"引用"}]},{"type":"text","text":"。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"当我们将某个变量（对象）赋值给指针（引用），实际上就是将这个变量（对象）的地址赋值给指针（引用）。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"codeblock","attrs":{"lang":"java"},"content":[{"type":"text","text":"p—>next = q; //表示p节点的后继指针存储了q节点的内存地址。\np—>next = p—>next—>next; //表示p节点的后继指针存储了p节点的下下个节点的内存地址。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":3},"content":[{"type":"text","text":"1.1指针指向哪儿"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"我们写链表代码时，使用的指针的"},{"type":"codeinline","content":[{"type":"text","text":"指来指去"}]},{"type":"text","text":"，很快就把我们搞糊涂了，在这种情况下很容易发生"},{"type":"codeinline","content":[{"type":"text","text":"指针丢失"}]},{"type":"text","text":"和"},{"type":"codeinline","content":[{"type":"text","text":"内存泄漏"}]},{"type":"text","text":"。我们先普及下这两个概念："}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"指针丢失"},{"type":"text","text":"：自己定义的指针不知道指到哪里了，没有明确的指向。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"内存泄漏"},{"type":"text","text":"：链表中的节点没有确切的指针判断，运行时会抛出空指针异常。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"我们以"},{"type":"codeinline","content":[{"type":"text","text":"插入节点"}]},{"type":"text","text":"和"},{"type":"codeinline","content":[{"type":"text","text":"删除结点"}]},{"type":"text","text":"来分析指针丢失和内存泄漏的具体情况"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"插入节点"}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"在节点a和节点b之间插入节点x，b是a的下一节点，p指针指向节点a，"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"codeblock","attrs":{"lang":"java"},"content":[{"type":"text","text":"p—>next = x;\nx—>next = p—>next; "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"这样的代码会造成指针丢失和内存泄漏，因为这会导致x节点的后继指针指向了自己本身。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"正确代码应该为："}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"codeblock","attrs":{"lang":"java"},"content":[{"type":"text","text":"x—>next = p—>next;\np—>next = x;"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/eb/ebe7935114019f64c193f798ba8b9e6f.png","alt":"image-20201103224355467","title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"删除节点"}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"同样的，在节点a和节点c之间删除节点b，b是a的下一节点，p指针指向节点a，正确的代码应该为："}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"codeblock","attrs":{"lang":"java"},"content":[{"type":"text","text":"p—>next = p—>next—>next;"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/fd/fd06426aba7ed8b869ad72907626bf44.png","alt":"image-20201103234222288","title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"在删除节点，考虑到删除的节点可能是链表中的第一个节点，我们通常在链表头部加入哨兵(头结点)，这样可以使得删除链表的代码是一致的，不用再额外考虑是否是第一个节点的情况。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"在链表加入哨兵的代码为"},{"type":"text","text":"："}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"codeblock","attrs":{"lang":"java"},"content":[{"type":"text","text":" //定义一个哨兵作为传入链表的头结点\n ListNode pre =new ListNode(0);\n pre.next=head;"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/3e/3ee8a7d34cadfdb33ced390c2126b07e.png","alt":"image-20201103233816980","title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":3},"content":[{"type":"text","text":"1.3判断边界的条件"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"处理链表问题时，要充分考虑链表的"},{"type":"codeinline","content":[{"type":"text","text":"边界判断条件"}]},{"type":"text","text":"，通常情况下，我们经常使用以下几种判断条件："}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"如果链表为空时，代码是否能正常工作？"}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"如果链表只包含一个结点时，代码是否能正常工作？"}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"如果链表只包含两个结点时，代码是否能正常工作？"}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"代码逻辑在处理头结点和尾结点的时候，是否能正常工作？"}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"这些判断条件需要结合自己的实际场景来使用"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"2、必须掌握的几类题目"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"在上面的学习中，我们对链表的一些易错的概念进行了解析，下面，我们就真正的代码实践，我在LeetCode上刷题时发现，链表题目通常分为以下几类："}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"单链表的反转(LeetCode206)"}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"链表中环的检测(LeetCode141)"}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"两个有序链表的合并(LeetCode21)"}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"删除链表(LeetCode18)"}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"删除链表倒数第n个结点(LeetCode19)"}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"求链表的中间结点(LeetCode876)"}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"这几类链表题基本涵盖了"},{"type":"codeinline","content":[{"type":"text","text":"大部分知识点"}]},{"type":"text","text":"，在下面的学习中，我们将一一攻克它，相信掌握它们之后，在以后"},{"type":"codeinline","content":[{"type":"text","text":"笔试/面试"}]},{"type":"text","text":"中，更能随心所欲。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":3},"content":[{"type":"text","text":"2.1单链表反转(LeetCode206)"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"思路"},{"type":"text","text":"：从前往后将每个节点的指针反向，即.next内的地址换成前一个节点的，但为了防止后面链表的丢失，在每次换之前需要先创建个指针指向下一个节点。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"codeblock","attrs":{"lang":"java"},"content":[{"type":"text","text":"class Solution {\n public ListNode reverseList(ListNode head) {\n\nif(head==null||head.next==null){\nreturn head;\n}\n ListNode p1=head;\n //用一个新的链表\n ListNode p2=null;\n while(p1!=null){\n //每次更换指向之前都需要保存下一个节点\n ListNode temp=p1.next;\n p1.next=p2;\n p2=p1;\n p1=temp;\n }\n return p2;\n }\n}"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":3},"content":[{"type":"text","text":"2.2链表中环的检测(LeetCode141)"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"思路"},{"type":"text","text":"：定义两个指针，p1和p2，指针p1每次走一步，指针p2每次走两步，如果链表中存在环，则必然会在某个时刻满足p1==p2"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"codeblock","attrs":{"lang":"java"},"content":[{"type":"text","text":"public class Solution {\n public boolean hasCycle(ListNode head) {\n if(head==null||head.next==null){\n return false;\n }\n ListNode slow=head;\n ListNode fast=head.next;\n while(fast!=null&&fast.next!=null){\n if(slow==fast){\n return true;\n }\n slow=slow.next;\n fast=fast.next.next;\n }\n return false;\n }\n}"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"NOTE"},{"type":"text","text":"：对于快指针来说，因为一次跳两步，如果要使用快指针作为判断条件，fast和fast.next都需要判断是否为空。("},{"type":"codeinline","content":[{"type":"text","text":"不可跨级"}]},{"type":"text","text":"）"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":3},"content":[{"type":"text","text":"2.3两个有序的链表合并(LeetCode21)"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"codeinline","content":[{"type":"text","text":"思路"}]},{"type":"text","text":"：可以新创建一个链表用于合并后的结果，合并的条件如下"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"两个链表都不为空"}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":">定义一个指针，查找合适的节点并放入新创建链表的下一位置"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"有一个链表为空"}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":">将不为空的链表放入新创建链表的下一位置"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"codeblock","attrs":{"lang":"java"},"content":[{"type":"text","text":"class Solution {\n public ListNode mergeTwoLists(ListNode l1, ListNode l2) {\n\n if(l1==null){\n return l2;\n }\n if(l2==null){\n return l1;\n }\n ListNode result=new ListNode(0);\n ListNode temp=result;\n //两个链表都不为空\n while(l1!=null&&l2!=null){\n if(l1.val<=l2.val){\n temp.next=l1;\n temp=temp.next;\n l1=l1.next;\n }\n else{\n temp.next=l2;\n temp=temp.next;\n l2=l2.next;\n }\n }\n //有一个链表为空\n if(l1==null){\n temp.next=l2;\n }\n else{\n temp.next=l1;\n }\n\n return result.next;\n }\n}"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":3},"content":[{"type":"text","text":"2.4删除链表(LeetCode18)"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"思路"},{"type":"text","text":"：可以在链表头加一个哨兵(头结点)，删除链表时先找到删除链表的上一个位置，按照删除规则删除即可。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"codeblock","attrs":{"lang":"java"},"content":[{"type":"text","text":"class Solution {\n public ListNode deleteNode(ListNode head, int val) {\n if(head==null){\n return null;\n }\n //定义一个哨兵作为传入链表的头结点\n ListNode pre =new ListNode(0);\n pre.next=head;\n \n ListNode temp=pre;\n while(temp!=null){\n if(temp.next.val==val){\n temp.next=temp.next.next;\n break;\n }\n else{\n temp=temp.next;\n }\n }\n return pre.next;\n }\n}"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":3},"content":[{"type":"text","text":"2.5删除链表倒数第 n 个结点(LeetCode19)"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"思路"},{"type":"text","text":"：删除节点时要利用好"},{"type":"codeinline","content":[{"type":"text","text":"哨兵"}]},{"type":"text","text":"(带头结点的链表)"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":">* 遍历数组的长度count"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":">* 找到要删除节点的前一个位置count-n-1"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":">* 删除节点"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"codeblock","attrs":{"lang":"java"},"content":[{"type":"text","text":"class Solution {\n public ListNode removeNthFromEnd(ListNode head, int n) {\n ListNode pre=new ListNode(0);\n pre.next=head;\n ListNode temp1=pre;\n ListNode temp2=pre;\n int count=0;\n while(temp1!=null){\n temp1=temp1.next;\n count++;\n }\n\n while(count-n-1>0){\n temp2=temp2.next;\n count--;\n }\n temp2.next=temp2.next.next;\n \n return pre.next;\n }\n}"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":3},"content":[{"type":"text","text":"2.6求链表的中间结点(LeetCode876)"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"思路"},{"type":"text","text":"：找出链表中结点的个数count，然后count/2找出中间结点，删除即可。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"codeblock","attrs":{"lang":"java"},"content":[{"type":"text","text":"class Solution {\n public ListNode middleNode(ListNode head) {\n if(head==null) return null;\n ListNode temp=head;\n int count=0;\n while(temp!=null){\n temp=temp.next;\n count++;\n }\n int mid=count/2;\n ListNode result=head;\n while(mid>0){\n result=result.next;\n mid--;\n }\n return result;\n }\n}"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"Note"},{"type":"text","text":":实践是检验真理的唯一标准，要真正的学好链表这个知识点，仅仅学理论是不可靠的，我们需要"},{"type":"codeinline","content":[{"type":"text","text":"多敲代码"}]},{"type":"text","text":"，"},{"type":"codeinline","content":[{"type":"text","text":"多思考"}]},{"type":"text","text":"，"},{"type":"codeinline","content":[{"type":"text","text":"多写多练"}]},{"type":"text","text":"，针对抽象的题目，可以"},{"type":"codeinline","content":[{"type":"text","text":"举例画图"}]},{"type":"text","text":"，来辅助的自己的思考。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"3、学习链表的体会"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"1、 函数中需要移动链表时，最好"},{"type":"codeinline","content":[{"type":"text","text":"新建一个指针来移动"}]},{"type":"text","text":"，以免更改原始指针位置。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"2、 单链表有"},{"type":"codeinline","content":[{"type":"text","text":"带头节点"}]},{"type":"text","text":"和"},{"type":"codeinline","content":[{"type":"text","text":"不带头结点"}]},{"type":"text","text":"的链表之分，一般做题"},{"type":"codeinline","content":[{"type":"text","text":"默认头结点是有值的"}]},{"type":"text","text":"。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"3、 链表的内存时"},{"type":"codeinline","content":[{"type":"text","text":"不连续"}]},{"type":"text","text":"的，一个节点占一块内存，每块内存中有一块位置（next）存放下一节点的地址。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"3、 链表中找"},{"type":"codeinline","content":[{"type":"text","text":"环"}]},{"type":"text","text":"的思想："},{"type":"codeinline","content":[{"type":"text","text":"快慢指针"}]},{"type":"text","text":"，创建两个指针，"},{"type":"codeinline","content":[{"type":"text","text":"一个快指针：一次走两步"}]},{"type":"text","text":"，"},{"type":"codeinline","content":[{"type":"text","text":"一个慢指针：一次走一步"}]},{"type":"text","text":"，若相遇则有环，若指向null则无环。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"4、 链表找"},{"type":"codeinline","content":[{"type":"text","text":"倒数第k个节点思想"}]},{"type":"text","text":"：创建"},{"type":"codeinline","content":[{"type":"text","text":"两个指针"}]},{"type":"text","text":"，第一个指针查询链表中结点的个数"},{"type":"codeinline","content":[{"type":"text","text":"count"}]},{"type":"text","text":"，然后"},{"type":"codeinline","content":[{"type":"text","text":"count-k"}]},{"type":"text","text":"确定删除结点的位置，用第二个指针遍历链表到"},{"type":"codeinline","content":[{"type":"text","text":"count-n-1"}]},{"type":"text","text":"个位置。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"5、 反向链表思想："},{"type":"codeinline","content":[{"type":"text","text":"从前往后"}]},{"type":"text","text":"将每个节点的指针反向，"},{"type":"codeinline","content":[{"type":"text","text":"即next内的地址换成前一个节点的"}]},{"type":"text","text":"，但为了防止后面链表的丢失，在每次换之前需要"},{"type":"codeinline","content":[{"type":"text","text":"先创建个指针指向下一个节点"}]},{"type":"text","text":"。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"总结"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"无论学习任何一个知识点，我们都需要在掌握"},{"type":"codeinline","content":[{"type":"text","text":"术(使用方法)"}]},{"type":"text","text":"的基础上，学习"},{"type":"codeinline","content":[{"type":"text","text":"道(本源)"}]},{"type":"text","text":"，学习数据结构与算法也是一样，我们不仅要掌握"},{"type":"codeinline","content":[{"type":"text","text":"如何使用它"}]},{"type":"text","text":"，更要掌握"},{"type":"codeinline","content":[{"type":"text","text":"为什么要是用它"}]},{"type":"text","text":"，相比其它的方法，"},{"type":"codeinline","content":[{"type":"text","text":"它有什么优点"}]},{"type":"text","text":"，难道是"},{"type":"codeinline","content":[{"type":"text","text":"时间复杂度低"}]},{"type":"text","text":"，"},{"type":"codeinline","content":[{"type":"text","text":"空间复杂度小"}]},{"type":"text","text":"，还是它的数据结构"},{"type":"codeinline","content":[{"type":"text","text":"适合这个场景等等"}]},{"type":"text","text":"..."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"参考文献"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"[1]王争.数据结构与算法之美"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"[2]LeetCode中国网站"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"刷题组合拳推荐"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"笔者在过去的3个月时间里整理常用的"},{"type":"codeinline","content":[{"type":"text","text":"数据结构与算法"}]},{"type":"text","text":"和"},{"type":"codeinline","content":[{"type":"text","text":"秒杀剑指offer"}]},{"type":"text","text":"，公众号分别回复"},{"type":"codeinline","content":[{"type":"text","text":"数据结构与算法"}]},{"type":"text","text":"，"},{"type":"codeinline","content":[{"type":"text","text":"秒杀剑指offer"}]},{"type":"text","text":"，即可领取两套电子书，希望能够帮助大家。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/1a/1ae1dba8ace02f8f893ab20b15cecbba.png","alt":null,"title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/6c/6c27702bae816147b22b79ffc0a6acb8.png","alt":null,"title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"我是"},{"type":"codeinline","content":[{"type":"text","text":"Simon郎"}]},{"type":"text","text":"，一个想要每天博学一点点的小青年，关注我，让我们一起进阶，一起博学。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/95/956573d023ad43fa3e2e6b8f5e6cecb0.png","alt":null,"title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}}]}