After brushing leetcode's linked list topic, I found a secret!

{"type":"doc","content":[{"type":"heading","attrs":{"align":null,"level":1},"content":[{"type":"text","text":" It's painted LeetCode The linked list topic of , I found a secret ！"}]},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":" introduction "}]},{"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":" Linked list "}]},{"type":"text","text":" It's nodes （node） Stored "},{"type":"codeinline","content":[{"type":"text","text":" Chain storage structure "}]},{"type":"text","text":", One node Contains a data Domain （ Storing data ） And a next Domain （ Store the next one node The pointer to ）, The nodes of a linked list are not necessarily continuous , It can be divided into "},{"type":"codeinline","content":[{"type":"text","text":" Leading node "}]},{"type":"text","text":" and "},{"type":"codeinline","content":[{"type":"text","text":" No leading node "}]},{"type":"text","text":". The head node contains only next Domain ."}]},{"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":" If you're not familiar with linked lists ,"},{"type":"link","attrs":{"href":"https://mp.weixin.qq.com/s/BOPP8JpDWNCqUfK8_SZtoA","title":""},"content":[{"type":"text","text":" It is suggested to read one of my articles first "}]},{"type":"text","text":". In this article , Mainly explains the use of linked list tips , How to use these skills to solve problems , In depth analysis of "},{"type":"codeinline","content":[{"type":"text","text":"LeetCode"}]},{"type":"text","text":" There is "},{"type":"codeinline","content":[{"type":"text","text":" Representative "}]},{"type":"text","text":" The title of the linked list of , believe me , After reading this article , You don't have to worry about lists anymore ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"1、 Several concepts of linked list "}]},{"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":" in fact , The structure of the linked list is relatively simple , What hinders our understanding of linked lists is often due to the... Of lists "},{"type":"codeinline","content":[{"type":"text","text":" The pointer "}]},{"type":"text","text":"、"},{"type":"codeinline","content":[{"type":"text","text":" The boundary problem "}]},{"type":"text","text":" etc. , This can make us very upset sometimes , Don't panic , Let's analyze the concepts one by one , I believe you will get something from it ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":3},"content":[{"type":"text","text":"1.1 What is the pointer in the linked list "}]},{"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":" We learn C Language , I've learned the pointer , It describes pointing to a "},{"type":"codeinline","content":[{"type":"text","text":" Memory address "}]},{"type":"text","text":", stay Java In language , There is no pointer , But we can think of it as "},{"type":"codeinline","content":[{"type":"text","text":" quote "}]},{"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":" When we put a variable （ object ） Assign a value to a pointer （ quote ）, In fact, it's the variable （ object ） Assign the address to the pointer （ quote ）."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"codeblock","attrs":{"lang":"java"},"content":[{"type":"text","text":"p—>next = q; // Express p A subsequent pointer to a node stores q The memory address of the node .\np—>next = p—>next—>next; // Express p A subsequent pointer to a node stores p The memory address of the next node of the node ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":3},"content":[{"type":"text","text":"1.1 Where does the pointer point to "}]},{"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":" When we write linked list code , Of the pointer used "},{"type":"codeinline","content":[{"type":"text","text":" Pointing to and fro "}]},{"type":"text","text":", It soon confused us , It's easy to happen in this situation "},{"type":"codeinline","content":[{"type":"text","text":" The pointer is missing "}]},{"type":"text","text":" and "},{"type":"codeinline","content":[{"type":"text","text":" Memory leak "}]},{"type":"text","text":". Let's popularize these two concepts first ："}]},{"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":" The pointer is missing "},{"type":"text","text":"： I don't know where the self-defined pointer is , There is no clear direction to ."}]},{"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":" Memory leak "},{"type":"text","text":"： The nodes in the linked list have no exact pointer judgment , The runtime throws a null pointer exception ."}]},{"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":" We use "},{"type":"codeinline","content":[{"type":"text","text":" Insert node "}]},{"type":"text","text":" and "},{"type":"codeinline","content":[{"type":"text","text":" Delete node "}]},{"type":"text","text":" To analyze the specific situation of pointer loss and memory leak "}]},{"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":" Insert node "}]}]}]},{"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":" At the node a And nodes b Insert nodes between x,b yes a The next node of ,p The pointer points to the node 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":" Such code can cause pointer loss and memory leak , Because it can lead to x The node's subsequent pointer points to itself ."}]},{"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":" The correct code should be ："}]},{"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":" Delete node "}]}]}]},{"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":" alike , At the node a And nodes c Delete nodes between b,b yes a The next node of ,p The pointer points to the node a, The correct code should be ："}]},{"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":" Deleting nodes , Consider that the deleted node may be the first node in the list , We usually put sentinels at the head of the list ( Head node ), In this way, the code for deleting the linked list is consistent , There is no need to consider whether it is the first node ."}]},{"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":" Add the code of sentry in the linked list as "},{"type":"text","text":"："}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"codeblock","attrs":{"lang":"java"},"content":[{"type":"text","text":" // Define a sentinel as the head node of the incoming list \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 The conditions for judging the boundary "}]},{"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":" When dealing with linked list problems , To fully consider the linked list of "},{"type":"codeinline","content":[{"type":"text","text":" Boundary conditions "}]},{"type":"text","text":", Usually , We often use the following judgment conditions ："}]},{"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":" If the linked list is empty , Whether the code works properly ？"}]}]}]},{"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":" If the linked list contains only one node , Whether the code works properly ？"}]}]}]},{"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":" If the linked list contains only two nodes , Whether the code works properly ？"}]}]}]},{"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":" Code logic deals with head and tail nodes , Whether it works properly ？"}]}]}]},{"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":" These judgment conditions need to be combined with their own actual scenarios "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"2、 What kinds of topics must be mastered "}]},{"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":" In the above study , We analyze some fallible concepts of linked list , below , We're really practicing code , I am here LeetCode I found out that , Linked list titles are usually divided into the following categories ："}]},{"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":" Inversion of single linked list (LeetCode206)"}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Detection of links in linked lists (LeetCode141)"}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The combination of two ordered linked lists (LeetCode21)"}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Delete linked list (LeetCode18)"}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Delete the last from the list n Nodes (LeetCode19)"}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Find the middle node of the linked list (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":" These kinds of linked list questions basically cover "},{"type":"codeinline","content":[{"type":"text","text":" Most of the knowledge "}]},{"type":"text","text":", In the following study , We will conquer it one by one , Believe that after mastering them , In the future "},{"type":"codeinline","content":[{"type":"text","text":" written examination / interview "}]},{"type":"text","text":" in , You can do whatever you want ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":3},"content":[{"type":"text","text":"2.1 Single linked list inversion (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":" Ideas "},{"type":"text","text":"： Reverse the pointer of each node from front to back , namely .next Change the address in to the previous node's , But in order to prevent the loss of the following list , Before each switch, you need to create a pointer to the next node ."}]},{"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 // With a new linked list \n ListNode p2=null;\n while(p1!=null){\n // Save the next node before each point change \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 Detection of links in linked lists (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":" Ideas "},{"type":"text","text":"： Define two pointers ,p1 and p2, The pointer p1 One step at a time , The pointer p2 Take two steps at a time , If there are rings in the list , Will be satisfied at some time 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":"： For fast pointers , Because two steps at a time , If you want to use the fast pointer as the judgment condition ,fast and fast.next We need to judge whether it is empty .("},{"type":"codeinline","content":[{"type":"text","text":" You can't cross levels "}]},{"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 Merge two ordered linked lists (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":" Ideas "}]},{"type":"text","text":"： You can create a new linked list for the merged results , The conditions for the merger are as follows "}]},{"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":" Neither list is empty "}]}]}]},{"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":"> Define a pointer , Find the appropriate node and place it in the next location of the newly created linked list "}]},{"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":" A linked list is empty "}]}]}]},{"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":"> Put the non empty linked list into the next position of the newly created list "}]},{"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 // Neither list is empty \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 // A linked list is empty \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 Delete linked list (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":" Ideas "},{"type":"text","text":"： You can add a sentinel to the head of the chain ( Head node ), When deleting a linked list, first find the last location of the deleted list , Delete according to the deletion rules ."}]},{"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 // Define a sentinel as the head node of the incoming list \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 Delete the last from the list n Nodes (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":" Ideas "},{"type":"text","text":"： When deleting nodes, make good use of "},{"type":"codeinline","content":[{"type":"text","text":" sentry "}]},{"type":"text","text":"( A linked list with leading nodes )"}]},{"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":">* Traverse the length of the array count"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":">* Find the previous location where you want to delete the node count-n-1"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":">* Delete node "}]},{"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 Find the middle node of the linked list (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":" Ideas "},{"type":"text","text":"： Find the number of nodes in the list count, then count/2 Find the middle node , Delete it ."}]},{"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":": Practice is the only criterion for testing truth , To really learn the knowledge of linked list , It's not reliable to study theory alone , We need to "},{"type":"codeinline","content":[{"type":"text","text":" Knock more code "}]},{"type":"text","text":","},{"type":"codeinline","content":[{"type":"text","text":" Think more "}]},{"type":"text","text":","},{"type":"codeinline","content":[{"type":"text","text":" Write more and practice more "}]},{"type":"text","text":", For abstract topics , Sure "},{"type":"codeinline","content":[{"type":"text","text":" For example, draw a picture "}]},{"type":"text","text":", To help your own thinking ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"3、 Experience of learning linked list "}]},{"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、 When you need to move the linked list in the function , best "},{"type":"codeinline","content":[{"type":"text","text":" Create a new pointer to move "}]},{"type":"text","text":", To avoid changing the original pointer position ."}]},{"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、 The single chain list has "},{"type":"codeinline","content":[{"type":"text","text":" Leading node "}]},{"type":"text","text":" and "},{"type":"codeinline","content":[{"type":"text","text":" No leading node "}]},{"type":"text","text":" Of the linked list of , Generally speaking, I do some questions "},{"type":"codeinline","content":[{"type":"text","text":" The default header node has a value "}]},{"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、 The memory of the linked list "},{"type":"codeinline","content":[{"type":"text","text":" Discontinuous "}]},{"type":"text","text":" Of , A node occupies a block of memory , There is a location in each block of memory （next） Store the address of the next node ."}]},{"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、 Look in the linked list "},{"type":"codeinline","content":[{"type":"text","text":" Ring "}]},{"type":"text","text":" Thought ："},{"type":"codeinline","content":[{"type":"text","text":" Speed pointer "}]},{"type":"text","text":", Create two pointers ,"},{"type":"codeinline","content":[{"type":"text","text":" A quick pointer ： Two steps at a time "}]},{"type":"text","text":","},{"type":"codeinline","content":[{"type":"text","text":" A slow pointer ： One step at a time "}]},{"type":"text","text":", If we meet, there is a ring , If it points to null Then there is no ring ."}]},{"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、 Link list to find "},{"type":"codeinline","content":[{"type":"text","text":" Last but not least k A node idea "}]},{"type":"text","text":"： establish "},{"type":"codeinline","content":[{"type":"text","text":" Two pointers "}]},{"type":"text","text":", The first pointer queries the number of nodes in the linked list "},{"type":"codeinline","content":[{"type":"text","text":"count"}]},{"type":"text","text":", then "},{"type":"codeinline","content":[{"type":"text","text":"count-k"}]},{"type":"text","text":" Determine where to delete the node , Use the second pointer to traverse the linked list to "},{"type":"codeinline","content":[{"type":"text","text":"count-n-1"}]},{"type":"text","text":" A place ."}]},{"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、 The idea of reverse linked list ："},{"type":"codeinline","content":[{"type":"text","text":" Before and after "}]},{"type":"text","text":" Reverse the pointer of each node ,"},{"type":"codeinline","content":[{"type":"text","text":" namely next Change the address in to the previous node's "}]},{"type":"text","text":", But in order to prevent the loss of the following list , You need to... Before each change "},{"type":"codeinline","content":[{"type":"text","text":" First create a pointer to the next node "}]},{"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":" summary "}]},{"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":" No matter learning any knowledge point , We all need to master "},{"type":"codeinline","content":[{"type":"text","text":" Technique ( Usage method )"}]},{"type":"text","text":" On the basis of , Study "},{"type":"codeinline","content":[{"type":"text","text":" Avenue ( origin )"}]},{"type":"text","text":", The same is true for learning data structures and algorithms , We should not only master "},{"type":"codeinline","content":[{"type":"text","text":" How to use it "}]},{"type":"text","text":", More to master "},{"type":"codeinline","content":[{"type":"text","text":" Why use it "}]},{"type":"text","text":", Compared with other methods ,"},{"type":"codeinline","content":[{"type":"text","text":" What are the advantages of it "}]},{"type":"text","text":", Is it "},{"type":"codeinline","content":[{"type":"text","text":" Low time complexity "}]},{"type":"text","text":","},{"type":"codeinline","content":[{"type":"text","text":" Small space complexity "}]},{"type":"text","text":", Or its data structure "},{"type":"codeinline","content":[{"type":"text","text":" Suitable for this scene and so on "}]},{"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":" reference "}]},{"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] Wang Zhan . The beauty of data structure and algorithm "}]},{"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 China website "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":" It is recommended to brush the title "}]},{"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":" The author in the past 3 Organize the common ones in a month "},{"type":"codeinline","content":[{"type":"text","text":" Data structure and algorithm "}]},{"type":"text","text":" and "},{"type":"codeinline","content":[{"type":"text","text":" Second kill sword finger offer"}]},{"type":"text","text":", The official account was answered separately "},{"type":"codeinline","content":[{"type":"text","text":" Data structure and algorithm "}]},{"type":"text","text":","},{"type":"codeinline","content":[{"type":"text","text":" Second kill sword finger offer"}]},{"type":"text","text":", You can get two sets of e-books , I hope I can help you ."}]},{"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":" I am a "},{"type":"codeinline","content":[{"type":"text","text":"Simon Lang "}]},{"type":"text","text":", A young man who wants to learn a little bit every day , Pay attention to me , Let's advance together , Learn together ."}]},{"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}}]}