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

This article introduces the knowledge of "what are the tips for linked lists". In the operation of actual cases, many people will encounter such a dilemma. Next, let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Linked list

Linked list is a very basic but love to test the linear structure of the data structure, the operation of the linked list is relatively simple, but it is very suitable to examine the interviewer's ability to write code, as well as the processing of corner case, as well as the application of pointers can easily cause NPE (null pointer exception). Considering the above reasons, the linked list is very important in the interview.

When it comes to linked lists, you have to mention arrays, which can be said to be the basis of data structures, so the main differences between them are:

Arrays must be contiguous in physical memory

Linked lists do not need to be continuous in physical memory and are connected by pointers.

So the best property of an array is that it can access random access randomly, and with index, it can access elements at O (1) time.

Because the linked list is discontinuous, it can not locate any element in O (1) time, so it can only be traversed from scratch.

This leads to the difference in efficiency between them in addition, deletion and modification.

In addition, the structure of the linked list itself is completely different from that of the array.

LinkedList is implemented by ListNode:

Class ListNode {int value; ListNode next;}

The structure looks like this:

This is an one-way linked list, and the other is a two-way linked list, that is, there is a previous pointer pointing to the previous node of the current node:

Class ListNode {int value; ListNode next; ListNode prev;}

In fact, the linked list-related questions are not very difficult, there are only a few routines, of which the most common test is the most basic question is to reverse the linked list, I heard that Microsoft can use this question to wipe out half of the candidate, the two methods of bug free is not easy. The article has been written before, click here to review.

Today we will talk about the two main skills in the linked list: double pointer method and dummy node. I believe that after reading this article, you can solve most of the problems related to the linked list.

Double pointer method

The double pointer method is used in many data structures and questions, and the speed pointer is the most commonly used in the linked list.

As the name implies, one of the two pointers is fast and the other is slow. The advantage is that it is easy to find the target location by traversing the linked list at different speeds.

Common problems such as finding the midpoint of a linked list or determining whether a linked list has rings.

Example 1: find the midpoint

This question is to give a linked list, and then find its midpoint, if it is odd, it is easy to do, if it is even, the question requires to return the second.

For example:

1-> 2-> 3-> 4-> 5-> NULL. You need to return the ListNode of 3.

1-> 2-> 3-> 4-> 5-> 6-> NULL, you need to return the ListNode of 4.

But actually complain, if I really want to design such an API, I prefer to return to the first midpoint of even numbers.

Why?

The algorithm problems are all abstractions of some problems in industrial production. For example, the purpose of finding the midpoint is to break the list, so if I return 3, I can disconnect 3 and 4; but if I return 4, how can I break the place before 4 on the one-way list? We have to do it again, please.

Solution

Method 1.

The most intuitive solution to this problem is that you can first find the length of the linked list, and then go half of that length to get the midpoint.

Class Solution {public ListNode middleNode (ListNode head) {if (head = = null) {return null;} int len = 0; ListNode current = head; while (current! = null) {len++; currentcurrent = current.next;} len / = 2; ListNode result = head While (len > 0) {resultresult = result.next; len--;} return result;}}

Method 2. Fast and slow pointer

We traverse the linked list with two pointers together, each time the fast pointer takes two steps and the slow pointer takes one step, so that when the fast pointer reaches the end, the slow pointer should be just in the midpoint of the linked list.

Class Solution {public ListNode middleNode (ListNode head) {ListNode slow = head; ListNode fast = head; while (fast! = null & & fast.next! = null) {slowslow = slow.next; fastfast = fast.next.next;} return slow;}}

Which of these two methods is better or worse?

On the Internet, a lot of people say that the method has been linked twice, and the second method has been passed only once.

But in fact, but method 2 uses two pointers to traverse, so the number of times passed by both methods is the same.

The biggest difference between them is:

Method one is offline algorithm, method two is online algorithm.

The amount of data in the company is endless, for example, customers are always placing orders in e-commerce systems, and the growth of friends in social software is always on the rise. these are data stream data stream, and we can't calculate the length of the data stream.

Then online algorithm can give the current results to the moment, needless to say that after all the data has been entered, it will not be finished. This is where online algorithm has a big advantage over offline algorithm.

For more explanations, you can refer to stack overflow's question, which is linked at the end of the article.

Example 2: judge whether a single linked list has a ring

Idea: the fast and slow pointers start from the head together, each time the fast pointer takes two steps, the slow pointer only takes one step, if there is a ring, then the two pointers must meet.

This is a typical race between the tortoise and the hare, or when running laps on the playground, students who run fast will always run slowly in loops.

Public class Solution {public boolean hasCycle (ListNode head) {ListNode slow = head; ListNode fast = head; while (fast! = null & & fast.next! = null) {slowslow = slow.next; fastfast = fast.next.next; if (slow = = fast) {return true }} return false;}}

There is an upgraded version of this question, which requires a return to the starting point of the ring.

Example 3: returns the starting point of a ring with a ring list

I feel that this problem is not all an algorithm problem, but also a math problem.

Let's draw a conclusion:

Hongmeng official Strategic Cooperation to build HarmonyOS Technology Community

The fast and slow pointer starts from the head of the chain, and the point at which it meets is marked as M.

With two more pointers, one starts from the beginning and the other starts from M, and the meeting point is the starting point of cycle.

Let's first look at the abstract picture:

Suppose the fast and slow pointers meet for the first time at M point.

Here we set three variables to represent several important lengths in the linked list:

X: the length from the head of the chain to the beginning of the ring

Y: the length from the beginning of the ring to the M point

Z: the length from the M point to the beginning of the ring.

Note: because the ring has a direction, Y is not Z.

In fact, the only relationship we know is that the fast and slow pointers meet for the first time at M point. This is also the relationship we initially assumed.

The fast and slow pointer has an immutable truth: the length of the fast pointer is always twice the length of the slow pointer.

How long did the fast and slow pointers go when they met?

Fast pointer: X + Y + assumes a k circle

Slow pointer: X + Y

Then we can use this double relationship to list the following equations:

2 * (X + Y) = X + Y + kL

So X + Y = kL

And we notice that: y + Z = L, then we can get X = Z.

So when two pointers, one starts from the beginning and the other starts from the M point, the meeting point is the starting point of the ring.

Take a look at the code:

Public class Solution {public ListNode detectCycle (ListNode head) {ListNode slow = head; ListNode fast = head; while (fast! = null & & fast.next! = null) {slowslow = slow.next; fastfast = fast.next.next; if (slow = = fast) {ListNode x = head; ListNode y = slow; while (x! = y) {xx = x.next Yy = y.Next;} return x;}} return null;}}

There is another application for this question, that is, to find a number repeated in a specific array. We will not expand it here. If you are interested, do it.

Next, let's talk about the dummy node technique.

Dummy node

Dummy means "false" in Chinese, and dummy node can probably be translated into virtual nodes. If you have something more authentic, please let me know in the comments section.

Generally speaking, the use of dummy node is to precede the real head of the linked list with a node pointing to that head, in order to facilitate the manipulation of head.

For linked lists, head is the soul of linked lists, because both queries and other operations need to start from scratch. As the saying goes, catch the thief first, catch the head of a linked list, and grasp the whole linked list.

So when we need to make changes to the header of the existing linked list, or are not sure which header node is, we can add a dummyHead in advance, so that we can flexibly deal with the rest of the linked list, and finally remove the "false head" when we return.

Many times dummy node is not necessary, but it will be very convenient to use and reduce the discussion of corner case, so it is very recommended to use it.

Just talking and not practicing fake tricks, let's go straight to the question.

Example 4: merge two sorted linked lists

There are many solutions to this problem, for example, the most intuitive one is to use two pointers, then compare the size, and connect the small one to the final result.

But the trouble is that in the end, we don't know who is the head, and which linked list head is the head of the final result?

In this case, dummy node is very suitable.

First hold it here with a virtual head, construct the whole linked list, and then remove the fake one.

Let's look at the code ~

Class Solution {public ListNode mergeTwoLists (ListNode L1, ListNode L2) {if (L1 = = null) {return L2;} if (L2 = = null) {return L1;} ListNode dummy = new ListNode (0); ListNode ptr = dummy; while (L1! = null & & L2! = null) {if (l1.val < l2.val) {ptr.next = L1 L1l1 = L1.Next;} else {ptr.next = L2; l2l2 = L2.next} ptrptr = ptr.next;} if (L1 = = null) {ptr.next = L2;} else {ptr.next = L1;} return dummy.next;}}

There is also an upgraded version of this question, which is to merge k ordered linked lists. It's essentially the same, except that the comparator needs to be rewritten.

Example 5: delete a node

The meaning of this problem is to delete a node with a specific value in the linked list, there may be more than one, it may be at the beginning or at the end.

If the node to be deleted is in the header, the header of the new linked list is uncertain or empty. This is a good time to use dummy node to avoid these corner case discussions.

The idea of this question is: use two pointers.

Prev: points to the tail of the current new linked list

Curr: points to the ListNode that is currently being traversed

If curr = = target value, move directly to the next one

If curr! = target value, point prev to it and connect it.

It should be noted that in the end, the prev.next must be pointed to the null, otherwise, if the tail of the original linked list is the target value, it will not be removed.

The code is as follows:

Class Solution {public ListNode removeElements (ListNode head, int val) {ListNode dummy = new ListNode (0); ListNode prev = dummy; ListNode curr = head; while (curr! = null) {if (curr.val! = val) {prev.next = curr; prevprev = prev.next;} currcurr = curr.next;} prev.next = null; return dummy.next This is the end of "what are the tips for linked lists"? thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.