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

This article mainly shows you "what are the test questions on the surface of the Java chain", the content is simple and clear, hoping to help you solve your doubts, the following let the editor lead you to study and learn what are the test questions on the surface of the Java chain?

The first question

Topic: reverse a single linked list

Each node is unchanged, but only modifies the current direction of each node

Look at the picture and analyze:

Problem analysis:

Each node is immutable, you only need to change the current point of each node, the first node points to null, and the second node points to the first node.

Explanation of the problem:

We need to define four node variables

The head variable is equal to the header node

Cur = head

Prev = null

CurNext = cur.next

Step 1: curNext = cur.next

Step 2: cur.next = prev

Step 3: prev = cur

Step 4: cur = curNext

Let's take a look at the diagram.

Step 1: curNext = cur.next

Step 2: cur.next = prev

Step 3: prev = cur

Step 4: cur = curNext

These four steps make it a cycle, and let's take another cycle to show you.

Step 5: curNext = cur.next

Step 6: cur.next = prev

Step 7: prev = cur

Step 8: cur = curNext

So the two loops I think you can see very clearly, since there must be termination conditions for the loop, so we can take a look, when cur goes to the last byte, we still need cur.next = prev, then cur is null, and when it is null, the reverse ends. So the termination condition of our loop is cur! = null. In addition, we also need to determine whether the head pointing to the header node is null. If it is null, there is no linked list. Just return null. After the inversion is completed, the last node becomes the header node, so we can just return to prev, so we can write the code.

Code implementation:

Lass Solution {public ListNode reverseList (ListNode head) {if (head = = null) {return null;} ListNode cur = head; ListNode prev = null; while (cur! = null) {ListNode cutNext = cur.next; cur.next = prev; prev = cur; cur = cutNext;} return prev }}

Force buckle

Https://leetcode-cn.com/problems/reverse-linked-list/description/

The topic link is above, everyone must open the link to do it yourself.

Second question

Topic: given a non-empty single linked list with header node head, return the middle node of the linked list. If there are two intermediate nodes, the second intermediate node is returned.

Drawing analysis:

Problem analysis: the odd number returns the middle node, and the even number returns the second intermediate node, that is, the even number returns the third.

Explanation of the problem:

Similarly, let's define two reference variables

Both fast,slow reference variables are equal to the head header node

As shown in the figure:

We let fast take two steps at a time, and slow take two steps at a time. In odd cases, where fast.next is null,slow is the position of the middle node. Even-numbered case: where fast is null,low is the location of the intermediate node. The reason is why? If two people walk at the same time, the speed of the fast is twice as fast as that of the slow, so the distance is also twice as long. One has reached the end, and the other is half the distance. With this train of thought, we can write code. Similarly, we need to determine whether the linked list is null or not, and just return null directly for null.

Code implementation:

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

Force buckle

Https://leetcode-cn.com/problems/middle-of-the-linked-list/description/

The third question

Topic: input a linked list and output the last-to-last node in the linked list

Drawing analysis:

Explanation of the problem:

Similarly, let's define two reference variables

Both reference variables of fast,slow point to the header node

As shown in the figure:

If we are looking for the last-to-last K, from the K to the first to the last, we need to take the KMU1 step, so we first let fast take the KMUR 1 step. When we finish the KMUE 1 step, fast points to the last but one, then slow is the last K for us. If fast finishes the KMUI 1 step, fast does not point to the penultimate step, then at this time we let fast and slow go back together, and they are always short of KMul 1 step. When fast comes to the last node, the node that slow points to is the last K we are looking for. Here we also have to judge K, if the length of the K-linked list, we just return to null.

Code implementation:

Public class Solution {public ListNode FindKthToTail (ListNode head,int k) {if (k)

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.