Shulou(Shulou.com)06/03 Report--

This article mainly explains "how to master the linked list in the practice of the front-end algorithm system". The content of the explanation in the article is simple and clear, and it is easy to learn and understand. let's study and learn how to master the linked list in the front-end algorithm system.

Before practicing, let me clarify my point of view in order to avoid more misunderstandings about data structures and algorithms or this series.

I think there must be some students preparing for the interview, so you must have heard of the interview to build rockets and work screws. Many people have used this sentence to criticize the algorithmic interviews of some big Internet companies. Therefore, there is such a remark: apart from dealing with interviews, learning algorithms is actually useless.

I do not completely object to this sentence, because now, with the development of technological ecology, all of you who are at the forefront of the field have prepared enough wheels for you to use other people's solutions directly when you encounter general business problems. In addition, I have also seen a sentence, at first I thought it was bullshit, but later I thought it was a bit of truth:

Any technology that needs to cross a certain IQ threshold in order to master, will not be easily popular.

In other words: technology becomes simpler, others are more willing to use it, and it is easier to be popular.

This is also a true portrayal of the current technical frameworks: easy enough, simple enough, so simple that you don't need to know the complex details at the bottom.

So the question is, what is your value as a programmer with wisdom and talent?

I think the value depends on the problem you can solve. If you can draw a simple Button according to the design draft, you can finish it, other front-end students can also do it, and even the back-end students can almost do the effect, then what is the personal value at this time? It's just that it makes no difference to accomplish what most people can easily do in a position that can be replaced at any time, Zhang San to finish, or Li Si to do it.

But now if you are facing a complex engineering problem, you need to develop a scaffolding tool to assist the business, transform the framework source code to improve the scalability of the project, or analyze the reasons immediately in the face of serious performance problems. Then give the idea of the solution and balance in different factors, these are not what an amateur player can do in a short time, this is the place that reflects his own value.

Back to the algorithm itself, it represents part of your ability to solve more complex problems. Therefore, in the long run, it will have an imperceptible influence on our development. Let's move on to the part of the linked list. It is mainly divided into the following topics:

Reverse linked list

Reverse the list here are a total of three topics for everyone to train. They are the reversal of the in-situ single linked list, two groups of inverted linked lists and K groups of inverted linked lists, and the difficulty increases step by step.

In the interview, when you encounter a linked list, the frequency of the reverse topic is also one of the highest, so regard it as the training type at the beginning of the linked list. I hope you can pay enough attention to it.

NO.1 simple reverse linked list

Reverses a single linked list.

Example:

Input: 1-> 2-> 3-> 4-> 5-> NULL output: 5-> 4-> 3-> 2-> 1-> NULL

Source: question 206 of LeetCode

Circular solution

This problem is a classic topic in the linked list, which fully reflects that the operation idea of the data structure of the linked list is simple, but the implementation is not so simple.

What problems should we pay attention to in the implementation?

Save subsequent nodes. As a novice, it is easy to point the next pointer of the current node directly to the previous node, but in fact, the pointer of the next node of the current node is lost. Therefore, in the process of traversal, you need to save the next node first, and then manipulate the next to point to.

The sound of linked list structure is defined as follows:

Function ListNode (val) {this.val = val; this.next = null;}

The implementation is as follows:

/ * * @ param {ListNode} head * @ return {ListNode} * / let reverseList = (head) = > {if (! head) return null; let pre = null, cur = head; while (cur) {/ / key: save the value of the next node let next = cur.next; cur.next = pre; pre = cur; cur = next;} return pre }

Because the logic is relatively simple, the code is done in one go. But just finishing is not enough. For linked list problems, the habit of boundary checking can help us further ensure the quality of the code. Specifically:

When the head node is empty, we have handled it through ✅

When the linked list contains only one node, we want to return this node directly. For the above code, after entering the loop, pre is assigned to cur, that is, head, no problem, through ✅

Run on LeetCode and successfully AC ✌

However, as far as systematic training is concerned, it is too hasty to let the program pass. Later, we will try our best to solve the same problem in different ways so as to achieve the effect of comprehension. It is also the development of our own ideas. Sometimes we may be able to achieve a better solution.

Recursive solution

As the previous idea has been introduced very clearly, so here we paste the code, we have a good experience:

Let reverseList = (head) = > {let reverse = (pre, cur) = > {if (! cur) return pre; / / Save next node let next = cur.next; cur.next = pre; return reverse (cur, next);} return reverse (null, head);}

No.2 interval reversal

Reverses the linked list from position m to n. Please use a scan to complete the reversal.

Description: 1 ≤ m ≤ n ≤ linked list length.

Example:

Input: 1-> 2-> 3-> 4-> 5-> NULL, m = 2, n = 4 output: 1-> 4-> 3-> 2-> 5-> NULL

Source: question 92 of LeetCode

Train of thought

Compared with the previous one with the whole linked list reversed, this question is actually a change of soup. We still have two types of solutions: cyclic solution and recursive solution.

The problem you need to pay attention to is the preservation (or recording) of the front and rear nodes. What does that mean? Look at this picture and you'll see.

With regard to the definition of the front node and the back node, we should be able to see it more clearly on the diagram, which will be often used later.

The last problem in the inversion operation has been solved, so I won't repeat it here. It is worth noting that the work after the inversion, then the work after the reversal of the whole interval is actually a process of transferring flowers and trees, first pointing the next of the front node to the end of the interval, and then pointing the next of the beginning of the interval to the back node. Therefore, there are four nodes that need to be paid attention to in this question: the front node, the back node, the beginning of the interval and the end of the interval. Next, let's start the actual coding operation.

Cyclic solution

/ * * @ param {ListNode} head * @ param {number} m * @ param {number} n * @ return {ListNode} * / var reverseBetween = function (head, m, n) {let count = n-m; let p = dummyHead = new ListNode (); let pre, cur, start, tail; p.next = head; for (let I = 0; I

< m - 1; i ++) { p = p.next; } // 保存前节点 front = p; // 同时保存区间首节点 pre = tail = p.next; cur = pre.next; // 区间反转 for(let i = 0; i < count; i++) { let next = cur.next; cur.next = pre; pre = cur; cur = next; } // 前节点的 next 指向区间末尾 front.next = pre; // 区间首节点的 next 指向后节点(循环完后的cur就是区间后面第一个节点，即后节点) tail.next = cur; return dummyHead.next; }; 递归解法 对于递归解法，唯一的不同就在于对于区间的处理，采用递归程序进行处理，大家也可以趁着复习一下递归反转的实现。 var reverseBetween = function(head, m, n) { // 递归反转函数 let reverse = (pre, cur) =>

{if (! cur) return pre; / / Save next node let next = cur.next; cur.next = pre; return reverse (cur, next);} let p = dummyHead = new ListNode (); dummyHead.next = head; let start, end; / / interval head and tail node let front, tail; / / front node and rear node for (let I = 0; I

< m - 1; i++) { p = p.next; } front = p; //保存前节点 start = front.next; for(let i = m - 1; i < n; i++) { p = p.next; } end = p; tail = end.next; //保存后节点 end.next = null; // 开始穿针引线啦，前节点指向区间首，区间首指向后节点 front.next = reverse(null, start); start.next = tail; return dummyHead.next; } No.3 两个一组翻转链表 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 来源: LeetCode 第 24 题 示例: 给定 1->

2-> 3-> 4, you should return 2-> 1-> 4-> 3.

Train of thought

As shown in the figure, we first set up a virtual header node (dummyHead) to assist our analysis.

First put p in the position of dummyHead and record the nodes of p.next and p.next.next, that is, node1 and node2.

Then let node1.next = node2.next, and the effect:

Then let node2.next = node1, and the effect:

Finally, dummyHead.next = node2, the flip is complete. At the same time, the p pointer points to node1, and the effect is as follows:

According to this loop, if p.next or p.next.next is empty, a new set of nodes cannot be found, and the loop ends.

Cyclic solution

The idea is clear, in fact, the implementation is relatively easy, the code is as follows:

Var swapPairs = function (head) {if (head = = null | | head.next = = null) return head; let dummyHead = p = new ListNode (); let node1, node2; dummyHead.next = head; while ((node1 = p.next) & & (node2 = p.next.next)) {node1.next = node2.next; node2.next = node1; p.next = node2; p = node1 } return dummyHead.next;}

Recursive mode

Var swapPairs = function (head) {if (head = = null | | head.next = = null) return head; let node1 = head, node2 = head.next; node1.next = swapPairs (node2.next); node2.next = node1; return node2;}

After using recursion, do you feel that the code is very concise?

I hope you can have a good experience of the process of recursive calls. I believe that understanding is a great improvement for yourself.

No.4 K flip linked list

Give you a linked list and flip it in a group of k nodes. Please return to the flipped list.

K is a positive integer whose value is less than or equal to the length of the linked list.

If the total number of nodes is not an integral multiple of k, keep the last remaining nodes in their original order.

Example:

Given the linked list: 1-> 2-> 3-> 4-> 5 when k = 2, it should return: 2-> 1-> 4-> 3-> 5 when k = 3, it should return: 3-> 2-> 1-> 4-> 5.

Description:

Your algorithm can only use constant extra space.

You can't just change the value inside the node, but you need to actually exchange the node.

Source: question 25 of LeetCode

Train of thought

The idea is similar to the two-group flip in No.3. The only difference is that in the case of two groups, each group only needs to reverse two nodes, while in the case of K groups, the corresponding operation is to reverse the linked list of K elements.

Recursive solution

I think the recursive solution is easier to understand, so paste the code of the recursive method first.

The concepts of `head node 'and `tail node' in the comments of the following code are all for the linked list before inversion.

/ * * @ param {ListNode} head * @ param {number} k * @ return {ListNode} * / var reverseKGroup = function (head, k) {let pre = null, cur = head; let p = head; / / the following loop is used to check whether the following elements can form a set of for (let I = 0; I

< k; i++) { if(p == null) return head; p = p.next; } for(let i = 0; i < k; i++){ let next = cur.next; cur.next = pre; pre = cur; cur = next; } // pre为本组最后一个节点，cur为下一组的起点 head.next = reverseKGroup(cur, k); return pre; }; 循环解法 重点都放在注释里面了。 var reverseKGroup = function(head, k) { let count = 0; // 看是否能构成一组，同时统计链表元素个数 for(let p = head; p != null; p = p.next) { if(p == null && i < k) return head; count++; } let loopCount = Math.floor(count / k); let p = dummyHead = new ListNode(); dummyHead.next = head; // 分成了 loopCount 组，对每一个组进行反转 for(let i = 0; i < loopCount; i++) { let pre = null, cur = p.next; for(let j = 0; j < k; j++) { let next = cur.next; cur.next = pre; pre = cur; cur = next; } // 当前 pre 为该组的尾结点，cur 为下一组首节点 let start = p.next;// start 是该组首节点 // 开始穿针引线！思路和2个一组的情况一模一样 p.next = pre; start.next = cur; p = start; } return dummyHead.next; }; 环形链表 NO.1 如何检测链表形成环? 给定一个链表，判断链表中是否形成环。 思路 思路一: 循环一遍，用 Set 数据结构保存节点，利用节点的内存地址来进行判重，如果同样的节点走过两次，则表明已经形成了环。 思路二: 利用快慢指针，快指针一次走两步，慢指针一次走一步，如果两者相遇，则表明已经形成了环。 可能你会纳闷，为什么思路二用两个指针在环中一定会相遇呢? 其实很简单，如果有环，两者一定同时走到环中，那么在环中，选慢指针为参考系，快指针每次相对参考系向前走一步，终究会绕回原点，也就是回到慢指针的位置，从而让两者相遇。如果没有环，则两者的相对距离越来越远，永远不会相遇。 接下来我们来编程实现。 方法一: Set 判重 /** * @param {ListNode} head * @return {boolean} */ var hasCycle = (head) =>

{let set = new Set (); let p = head; while (p) {/ / the same node meets again, which means that there is a ring if (set.has (p)) return true; set.add (p); p = p.nextt;} return false;}

Method 2: fast and slow pointer

Var hasCycle = function (head) {let dummyHead = new ListNode (); dummyHead.next = head; let fast = slow = dummyHead; / / zero nodes or one node, definitely acyclic if (fast.next = = null | | fast.next.next = = null) return false; while (fast & & fast.next) {fast = fast.next.next; slow = slow.next / / the two met if (fast = = slow) {return true;}} return false;}

How does No.2 find the starting point of the ring

Given a linked list, returns the first node where the linked list begins to enter the ring. Returns null if the linked list has no loops.

* * Note: * * the given linked list is not allowed to be modified.

Train of thought analysis

We have just judged how to judge the occurrence of a ring, so how to find the node of the ring? Let's analyze a wave.

It looks cumbersome, so let's take it a little bit more abstract:

Set the speed pointer to walk for x seconds, and the slow pointer to walk once a second.

For fast pointer, there are: 2x-L = m * S + Y-①

For slow pointer, x-L = n * S + Y-②

Where m and n are natural numbers.

①-② * 2:

L = (m-n) * S-Y-③

Well, this is a very important equation. We now assume that there is a new pointer at the far left end of the L segment, and the slow pointer is still at the meeting place.

Let the new pointer and the slow pointer take one step at a time, so when the new pointer takes the L step, it reaches the starting point of the ring, while in the meantime, let's see what the slow pointer looks like.

From the ③ formula, the slow pointer has gone (m-n) * S-Y units, taking the starting point of the ring as the reference, and the position of the encounter is Y, but now by Y + (m-n) * S-Y, that is (m-n) * S, we know that the slow pointer actually refers to the starting point of the ring and walks the whole (m-n) circle. That is, the slow pointer also reaches the beginning of the ring at this time. : tip conclusion the current solution is very clear. When the fast and slow pointers meet, let the new pointer start from the beginning, move forward with the slow pointer at the same time, and one step at a time. The place where the two meet is the starting point of the ring. :::

Programming realization

Once you understand the principle, it will be much easier to implement.

/ * * @ param {ListNode} head * @ return {ListNode} * / var detectCycle = function (head) {let dummyHead = new ListNode (); dummyHead.next = head; let fast = slow = dummyHead; / / zero nodes or one node, definitely acyclic if (fast.next = = null | fast.next.next = = null) return null; while (fast & fast.next) {fast = fast.next.next Slow = slow.next; / / the two met if (fast = = slow) {let p = dummyHead; while (p! = slow) {p = p.next; slow = slow.next;} return p;}} return null;}

Linked list merge

NO.1 merges two ordered linked lists

Merge two ordered linked lists into a new ordered linked list and return. The new linked list is formed by splicing all the nodes of the given two linked lists.

Example:

Input: 1-> 2-> 4, 1-> 3-> 4 output: 1-> 1-> 2-> 3-> 4-> 4

Source: question 21 of LeetCode

Recursive solution

The recursive solution is easier to understand, so let's do it with recursion first:

/ * @ param {ListNode} L1 * @ param {ListNode} L2 * @ return {ListNode} * / var mergeTwoLists = function (L1, L2) {const merge = (L1, L2) > {if (L1 = = null) return L2; if (L2 = = null) return L1; if (l1.val > l2.val) {l2.next = merge (L1, l2.next); return L2 } else {l1.next = merge (l1.next, L2); return L1;}} return merge (L1, L2);}

Cyclic solution

Var mergeTwoLists = function (L1, L2) {if (L1 = = null) return L2; if (L2 = = null) return L1; let p = dummyHead = new ListNode (); let p1 = L1, p2 = L2; while (p1 & & p2) {if (p1.val > p2.val) {p.next = p2; p = p.nextt; p2 = p2.next } else {p.next = p1; p = p.next; p1 = p1.next;} / / be sure to check the rest of the if (p1) p.next = p1; else p.next = p2; return dummyHead.next;} after the loop is completed.

No.2 merges K ordered linked lists

Merge k sorted linked lists and return the merged sorted linked list. Please analyze and describe the complexity of the algorithm.

Example:

Input: [1-> 4-> 5, 1-> 3-> 4, 2-> 6] output: 1-> 1-> 2-> 3-> 4-> 4-> 5-> 6

Source: question 23 of LeetCode

Top-down (recursive) implementation

/ * * @ param {ListNode []} lists * @ return {ListNode} * / var mergeKLists = function (lists) {/ / var mergeTwoLists = function (L1, L2) {/ * above has been implemented * /}; const _ mergeLists = (lists, start, end) = > {if (end-start)

< 0) return null; if(end - start == 0)return lists[end]; let mid = Math.floor(start + (end - start) / 2); return mergeTwoList(_mergeLists(lists, start, mid), _mergeLists(lists, mid + 1, end)); } return _mergeLists(lists, 0, lists.length - 1); }; 自下而上实现 在这里需要提醒大家的是，在自下而上的实现方式中，我为每一个链表绑定了一个虚拟头指针(dummyHead)，为什么这么做? 这是为了方便链表的合并，比如 l1 和 l2 合并之后，合并后链表的头指针就直接是 l1 的 dummyHead.next 值，等于说两个链表都合并到了 l1 当中，方便了后续的合并操作。 var mergeKLists = function(lists) { var mergeTwoLists = function(l1, l2) {/*上面已经实现*/}; // 边界情况 if(!lists || !lists.length) return null; // 虚拟头指针集合 let dummyHeads = []; // 初始化虚拟头指针 for(let i = 0; i < lists.length; i++) { let node = new ListNode(); node.next = lists[i]; dummyHeads[i] = node; } // 自底向上进行merge for(let size = 1; size < lists.length; size += size){ for(let i = 0; i + size < lists.length;i += 2 * size) { dummyHeads[i].next = mergeTwoLists(dummyHeads[i].next, dummyHeads[i + size].next); } } return dummyHeads[0].next; }; 多个链表的合并到这里就实现完成了，在这里顺便告诉你这种归并的方式同时也是对链表进行归并排序的核心代码。希望你能好好体会自上而下和自下而上两种不同的实现细节，相信对你的编程内功是一个不错的提升。 求链表中间节点 判断回文链表 请判断一个单链表是否为回文链表。 示例1: 输入: 1->

2 output: false

Example 2:

Input: 1-> 2-> 2-> 1 output: true

Can you solve this problem with O (n) time complexity and O (1) space complexity?

Source: question 234 of LeetCode

Train of thought analysis

This question is actually very simple without taking into account performance limitations. But considering the O (n) time complexity and O (1) space complexity, it's probably worth stopping and thinking about it.

The requirement of the topic is a single linked list, and there is no way to access the previous node, so we have to find another way:

Find the midpoint of the linked list, then reverse the second half, and you can draw a conclusion by comparing it in turn. Next, let's achieve a wave.

Code implementation

In fact, the key part of the code is to find the right point. Light the sword first:

Let dummyHead = slow = fast = new ListNode (); dummyHead.next = head; / / pay attention to the while (fast & & fast.next) {slow = slow.next; fast = fast.next.next;}

You may wonder why the boundary is set like this.

We might as well analyze it and discuss it when the number of nodes in the split table is odd and even.

When the number of nodes in the chain table is odd

Try to simulate that when fast is empty, stop the loop with the following state:

When the number of nodes in the linked list is even

Walk through the simulation. When fast.next is empty, stop the loop. The status is as follows:

For the two conditions that fast is empty and fast.next is empty, in the case of odd number, fast always appears first, and in the case of even number, fast.next always appears first.

That is to say: once fast is empty, the number of nodes in the linked list must be odd, otherwise it is even. So the two cases can be discussed by merging. When fast is empty or fast.next is empty, the loop can be terminated.

The complete implementation is as follows:

/ * * @ param {ListNode} head * @ return {boolean} * / var isPalindrome = function (head) {let reverse = (pre, cur) = > {if (! cur) return pre; let next = cur.next; cur.next = pre; return reverse (cur, next);} let dummyHead = slow = fast = new ListNode (); dummyHead.next = head / / pay attention to the midpoint. Gold template while (fast & & fast.next) {slow = slow.next; fast = fast.next.next;} let next = slow.next; slow.next = null; let newStart = reverse (null, next); for (let p = head, newP = newStart; newP! = null P = p.next, newP = newP.next) {if (p.val! = newP.val) return false;} return true;} Thank you for your reading, the above is the content of "how to master the linked list in the front-end algorithm system practice". After the study of this article, I believe you have a deeper understanding of how to master the linked list in the front-end algorithm system practice. the specific use of the situation also needs to be verified by practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.