当前位置:网站首页>刷了LeetCode的链表专题,我发现了一个秘密!

刷了LeetCode的链表专题,我发现了一个秘密!

2020-11-06 01:15:00 InfoQ

{"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}}]}

版权声明
本文为[InfoQ]所创,转载请带上原文链接,感谢
https://xie.infoq.cn/article/380dad21eb1ac00eb1941564c?utm_source=rss&utm_medium=article