Java implementation chain surface test questions

This note has been sorted out for a whole week. Each line of code is written by yourself, and the test run is successful. At the same time, it also reviews the explanation related to the linked list in the book sword finger offer, hoping to be helpful to the written examination and interview.

This article contains the following contents of the linked list:

1. Creation and traversal of single linked list

2. Find the number of nodes in the single linked list

3. Find the penultimate node in the single link list (Sword finger offer, question 15)

4. Find the intermediate node in the single linked list

5. Merge two ordered single linked lists, and the merged linked list is still orderly [high frequency] (Sword finger offer, question 17)

6. The inversion of the single linked list [occurs most frequently] (Sword finger offer, question 16)

7. Print the single link list from end to end (Sword finger offer, question 5)

8. Judge whether the single linked list has a ring

9. Take out the length of the ring from the linked list

10. In the single chain list, take out the starting point of the ring (Sword finger offer, question 56). This question needs to use questions 8 and 9 above.

11. Judge the first intersection of two single linked lists (Sword finger offer, question 37)

1. Creation and traversal of single linked list:

In the above code, the nodes in this node are represented by internal classes (line 33). The greatest advantage of using internal classes is that they can access each other for private operations with external classes.

Note: internal class access is characterized by: internal classes can directly access members of external classes, including private classes; An object must be created before an external class can access members of an internal class.

To facilitate the addition and traversal operations, add a member variable current in the linklist class to represent the index of the current node (line 03).

In the method of traversing the linked list (20 lines), the parameter node indicates that the traversal starts from the node node, not necessarily from the head node.

2. Find the number of nodes in the single linked list:

Check whether the linked list is empty. The time complexity is O (n). This is relatively simple.

Core code:

3. Find the penultimate node in the single linked list:

3.1 general idea:

First traverse the entire linked list from beginning to end, calculate the length size of the linked list, and get the length of the linked list. It's easy to do. Just output the (size-k) node directly (note that when the linked list is empty, K is 0, K is 1, and K is greater than the number of nodes in the linked list)

）。 The time complexity is O (n), and the general idea is as follows:

What if the interviewer doesn't allow you to traverse the length of the linked list? Next is.

3.2 improvement idea: (this idea is also applied to other topics)

Here, you need to declare two pointers: two node type variables first and second. First, let both first and second point to the first node, and then move the second node back k-1. At this time, first and second are separated by k-1. Then move the two nodes backward as a whole until the second node reaches the last node, At this time, the position pointed by the first node is the position of the penultimate node. The time complexity is O (n)

Code implementation: (First Edition)

Code implementation: (final version) (throw an exception when k is greater than the number of nodes in the linked list)

In the above code, it seems that the function has been implemented, but it is not robust enough:

Note that K is equal to 0;

If K is greater than the number of nodes in the linked list, a null pointer exception will be reported, so you need to make a judgment here.

The core code is as follows:

4. To find intermediate nodes in a single linked list:

Similarly, the interviewer does not allow you to calculate the length of the linked list. What should you do?

Idea:

As in Section 2 above, two pointers, first and second, are also set, but here, the two pointers move forward at the same time. The second pointer moves two steps at a time, and the first pointer moves one step at a time until the second pointer reaches the last node. At this time, the node referred to by the first pointer is the intermediate node. Note that the linked list is empty and the number of nodes in the linked list is 1 and 2. The time complexity is O (n).

Code implementation:

In the above code, when n is an even number, the intermediate node obtained is the N / 2 + 1 node. For example, when the linked list has 6 nodes, the fourth node is obtained.

5. Merge two ordered single linked lists, and the merged linked list remains ordered:

This problem is often investigated by companies.

For example:

Linked list 1:

　　1->2->3->4

Linked list 2:

　　2->3->4->5

After consolidation:

　　1->2->2->3->3->4->4->5

Problem solving ideas:

Compare linked list 1 and linked list 2 next to each other.

This is similar to merge sort. In particular, pay attention to the case that both linked lists are empty and one of them is empty. Only O (1) space is required. The time complexity is O (max (len1, len2))

Code implementation:

Code test:

The add method and print method used in the above code are consistent with those in Section 1.

Operation effect:

Note: the sword finger offer is solved recursively, which is a little difficult to understand.

6. Reversal of single linked list: [highest frequency]

For example, linked list:

　　1->2->3->4

After reversal:

　　4->2->2->1

Idea:

Traverse the original linked list from beginning to end. Each node will be picked and placed at the front of the new linked list. Note that the linked list is empty and there is only one node. The time complexity is O (n)

Method 1: (traversal)

In the above code, the core code is lines 16 and 17.

Method 2: (recursive)

This method is a little difficult. I won't talk about it first.

7. Print a single linked list from end to end:

For this reverse order problem, we should think of stack, last in, first out. Therefore, this problem either uses the stack itself or allows the system to use the stack, that is, recursion. Note that the linked list is empty. The time complexity is O (n)

Note: don't think about reversing the single linked list first and then traversing the output, which will destroy the structure of the linked list. It's not recommended.

Method 1: (create a stack by yourself)

Method 2: (use the stack of the system: recursion, elegant and concise code)

Summary: Method 2 is implemented based on recursion. Diane looks concise and elegant, but there is a problem: when the linked list is very long, the level of method call will be very deep, which may cause stack overflow. The explicit stack of method 1 is based on loop implementation, and the robustness of the code is better.

8. Judge whether the single linked list has a ring:

Two pointers are also used here. If a linked list has a ring, you can never get to the end by traversing with one pointer.

Therefore, we use two pointers to traverse: the first pointer takes one step at a time and the second pointer takes two steps at a time. If the first pointer and the second pointer meet, it indicates that there is a ring. The time complexity is O (n).

method:

Full version code: (including test part)

Here, we also need to add an overloaded add (node node) method, which is used when creating a one-way circular linked list.

The code to detect whether the single linked list has a ring is line 50.

Line 88: we continue to add the head node to the linked list. At this time, the single linked list will be linked. The final running effect is true.

If 88 lines of code are deleted, the single linked list has no ring, and the operation effect is false.

9. Take out the linked list. The length of the link:

The linked list we usually encounter is the following: (Figure 1)

The length of the ring in the figure above is 4.

But it may also be the following: (Figure 2)

At this time, the length of the ring in the figure above is 3.

How do you find the length of the ring?

Idea:

Inside, We need to use the hascycle method in Section 7 above (the method to judge whether the linked list has a ring). The return value of this method is Boolean, but now we need to modify this method slightly to make its return value the node that meets. Then, it's easy for us to get the node that meets. This node must be in the ring. We can let the pointer corresponding to this node go down until it returns to the origin Then we can calculate the length of the ring.

method:

Full version code: (including test part)

Operation effect:

If the test code of lines 104 to 122 above is changed to the following: (that is, change the structure in Figure 2 to the structure in Figure 1)

Operation results:

If you delete line 8 in the above code, the linked list will have no rings, so the running result is 0.

10. In the single chain list, take out the starting point of the ring:

The linked list we usually encounter is the following: (Figure 1)

The starting point of the ring in the figure above is 1.

But it may also be the following: (Figure 2)

At this time, the starting point of the ring in the above figure is 2.

Method 1:

Here, we need to use the method getcyclelength to get the length of the ring in Section 8 above to obtain the length of the ring. After obtaining the length of the ring, you need to use two pointer variables first and second. First, let the second pointer take the length step; Then let the first pointer and the second pointer take one step at the same time. When the two pointers meet, the node when they meet is the starting point of the ring.

Note: in order to find the starting point of the ring, we need to obtain the length of the ring first, and in order to obtain the length of the ring, we need to judge whether there is a ring first. So there are actually three methods used.

Code implementation:

Core code of method 1:

Full version code: (including test part)

11. Judge the first intersection of two single linked lists:

The beauty of programming p193, 5.3, interview question 37 has this question.

During the interview, many people's first reaction when they encounter this problem is to traverse each node in order on the first linked list. When traversing a node, they traverse each node in order on the second linked list. If there is a node on the second linked list that is the same as the node on the first linked list, it means that the two linked lists coincide on this node. Obviously, the time complexity of this method is O (len1 * len2).

Method 1: adopt the idea of stack

We can see that the topological shape of two partially coincident linked lists with common nodes looks like a Y, not an X. As shown in the figure below:

As shown in the figure above, if the single linked list has common nodes, the last node (node 7) must be the same, and it starts from a middle node (node 6), and the subsequent nodes are the same.

The problem now is that in a single linked list, we can only traverse from the beginning of the node in order, and finally reach the tail node. The last arriving tail node has to be compared first. Does this sound like "first in and then out"? So we can think of using the characteristics of the stack to solve this problem: put the nodes of the two linked lists into the two stacks respectively, so that the tail nodes of the two linked lists are located at the top of the two stacks, and then compare the top of the next stack until the last same node is found.

In this idea, we need to use two auxiliary stacks. The space complexity is O (len1 + len2) and the time complexity is O (len1 + len2). Compared with the original brute force method, the time efficiency has been improved, which is equivalent to using space consumption for time efficiency.

So, is there a better way? Next.

Method 2: judge the first node where two linked lists intersect: use the speed pointer and recommend (better solution)

In the above method 2, we use the stack because we want to traverse to the tail nodes of two linked lists at the same time. In fact, we have a simpler way to solve this problem: first, traverse the two linked lists to get their length. In the second traversal, take steps | len1-len2 | on the longer linked list, and then traverse the two linked lists at the same time. The first same node found is their first intersection.

The time complexity of this idea is also o (len1 + len2), but we no longer need the auxiliary stack, so we improve the space efficiency. When the interviewer confirms our last idea, we can start writing code.

Core code:

The above is the classic interview question about Java linked list. I hope it can help you successfully pass the interview.