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

This article mainly explains "how to use debug debugging", the content of the article is simple and clear, easy to learn and understand, now please follow the editor's ideas slowly in depth, together to study and learn "how to use debug debugging" bar!

First, reverse the linked list (classic topic)

1.1.1 topic analysis

Reverse linked list is a classic topic, in which the information is described clearly. Given a single linked list, reverse it.

First of all, what are the ideas? From the case output given in the question, we can see whether we only need to change the pointer of the input linked list to the opposite direction to get the output result.

As shown in the following figure:

But the problem is that we are a single linked list, and there is no way to point the next node directly to the previous node of that node.

Therefore, you need to define an auxiliary pointer to point to the previous node of that node, so that it can be done, as shown in the following figure.

Then according to our above analysis, that is, point the cur pointer to the pre node.

Note: there is a pit here

How do we move the pointer down when we point the current node [cur] to the previous node [pre]?

At this point, the node [cur] has pointed to the previous node [pre], so we also need a temporary variable to hold the next node of the current node. For exactly why, let's debug the process in the following code demonstration.

Following our previous steps, move the pointer down, as shown in the figure.

After moving the pointer, the next pointer of the current node is pointed to the previous node.

Finally, when the current node has no next node, the traversal ends, as shown in the figure.

1.1.2 Code Analysis

According to the routine, initialize the node object first.

Class ListNode {int val; ListNode next; ListNode () {} ListNode (int val) {this.val = val;} ListNode (int val, ListNode next) {this.val = val; this.next = next;} @ Override public String toString () {return "ListNode {" + "val=" + val +'}';}}

Create a single linked list structure.

/ / create a single linked list ListNode L1 = new ListNode (1); ListNode L2 = new ListNode (2); ListNode L3 = new ListNode (3); ListNode L4 = new ListNode (4); ListNode L5 = new ListNode (5); NodeFun nodeFun = new NodeFun (); nodeFun.add (L1); nodeFun.add (L2); nodeFun.add (L3); nodeFun.add (L4) / / return the created linked list ListNode node = nodeFun.add (L5)

Reverses the code of the linked list.

Public ListNode reverseListIteration (ListNode head) {/ / define the current node auxiliary pointer ListNode pre = null; / / define the current node auxiliary pointer ListNode cur = head; / / Loop the current node is not null while (null! = cur) {/ / temporary variable holds the next node of the current node ListNode temp = cur.next / / the next of the current node points to the upper node cur.next = pre; / / the node moves down pre = cur; / / the current node points to the next node cur = cur.next;} return pre;} 1.1.3 debug debugging

Node initialization is completed. According to the analysis, we have defined 2 nodes. For example, the first traversal of [pre] node in the figure above is null, and [cur] starts from the first node.

In the next step of debug debugging, let's take a moment to review the question mentioned earlier: why should the next node of the current node be saved with a temporary variable? let's just look at debug debugging.

When traversing for the first time, after modifying the pointer, the current node has already pointed to the previous node, and then look at the illustration of the above topic analysis.

This is why the next node of the current node is cached first.

In the debug above, we can see that [cur] the pointer of the current node is already pointing to null, and the next step is to move the pointer to the next node.

We then proceed to debug debugging, and according to the above analysis, the second step of the loop is to point the node [2] to the previous node [1], as shown in the following figure.

Now that the current node [cur] has pointed to [2], its next node is [1], as shown in the following figure.

After the above two-step loop, the pointer is successfully reversed, and the rest of the node loop is exactly the same.

When the loop reaches the last node [5], the next node is null, which ends the while loop, and the node [5] points to the previous node [4].

Finally, let's take a look at the running results.

Second, palindromes linked list

1.2.1 topic analysis

If you have done a string algorithm problem, there is a palindrome string title. Yes, they both mean the same thing.

Look at the title description to know whether a linked list is a palindromic linked list, that is, to look at the linked list is to see if the right reading and reverse reading of the linked list are the same.

Let's say we get the second half of the linked list and reverse it. To compare with the first half of the linked list, the equivalent value is the palindrome linked list.

Note:

This method will destroy the structure of the original linked list, and finally reassemble the linked list in order to ensure the consistency of the topic.

Another way to solve the problem is to save the entire linked list node traversal into an array, and the array has a subscript, and the size of the array can be obtained directly, so you only need to judge from the beginning and end of the array.

We have shared a question on the reverse linked list, and now the focus is on how to get the second half of the linked list.

Let's talk about the idea of fast and slow pointers. Usually we define two pointers, one moving fast and the other moving slowly. For a detailed case, please refer to my previous article, "Open the algorithm, restore the problem, and understand each problem with debug debugging". There is a question about the speed pointer.

Define that the slow pointer moves 1 node at a time, and the fast pointer moves 2 nodes at a time. Of course, we need to make sure that the next node of the fast node is not empty.

Slow = slow.next;fast = fast.next.next

In fact, the idea of the fast and slow pointer is that if the linked list is a palindromic linked list, the fast pointer is one step more than the slow pointer, and when the fast pointer is finished, the slow pointer is just half of the linked list.

In the image above, the slow pointer goes to exactly half of the linked list, and then you get the second half of the linked list, that is, slow.next.

1.2.2 Code Analysis

The old routine, first create a palindrome linked list.

ListNode L1 = new ListNode (1); ListNode L2 = new ListNode (2); ListNode L3 = new ListNode (2); ListNode L4 = new ListNode (1); NodeFun nodeFun = new NodeFun (); nodeFun.add (L1); nodeFun.add (L2); nodeFun.add (L3); ListNode head = nodeFun.add (L4)

Gets the second half of the linked list code.

Private ListNode endOfFirstHalf (ListNode head) {ListNode fast = head; ListNode slow = head; while (fast.next! = null & & fast.next.next! = null) {fast = fast.next.next; slow = slow.next;} return slow;}

The code for reversing the linked list is the same as the previous topic.

Finally, the two linked lists are determined whether they are the same.

/ / determine whether palindromes ListNode p1 = head; ListNode p2 = secondHalfStart; boolean flag = true; while (flag & & p2! = null) {if (p1.val! = p2.val) {flag = false;} p1 = p1.next; p2 = p2.next;} 1.2.3 debug debugging

First get the second half of the linked list.

After debug starts the loop, fast goes directly to the third node of the linked list [2]

Slow.next is the second half of the linked list, and then reverse the latter part of the linked list.

In the end, we get the following two linked lists.

Finally, the two linked lists are compared to see if they are equal, and equality is a palindrome linked list.

Third, the middle node of the linked list

1.3.1 topic analysis

At first glance, the middle node of getting a linked list is similar to using a fast or slow pointer to get the second half of a linked list in a palindrome linked list.

Yes, this wave of operation is similar, but not exactly the same, the main idea is the speed pointer.

In other words, if you have understood the above question, it is not a big deal. Without saying much, let's analyze the wave first.

Similarly, we define that the slow slow pointer moves one node at a time, and the fast fast pointer moves 2 nodes at a time.

So when the fast fast pointer moves to the last node, the slow slow pointer is the linked list to return.

I wonder if you have a question. That is why the slow pointer moves one node and the fast node moves two nodes? If it is an even number of nodes, this rule is still correct! Then verify it.

For convenience, continue traversing the nodes above.

It is described in the title that if there are two intermediate nodes, the second node is returned, so the return node [4p5] also meets the requirements.

1.3.2 Code Analysis

Create a linked list structure.

ListNode L1 = new ListNode (1); ListNode L2 = new ListNode (2); ListNode L3 = new ListNode (3); ListNode L4 = new ListNode (4); ListNode L5 = new ListNode (5); NodeFun nodeFun = new NodeFun (); nodeFun.add (L1); nodeFun.add (L2); nodeFun.add (L3); nodeFun.add (L4); ListNode head = nodeFun.add (L5)

Gets the second half of the linked list code.

/ / Fast and slow pointer ListNode slow = head; ListNode fast = head; while (fast! = null & & fast.next! = null) {/ / move pointer fast = fast.next.next; slow = slow.next;} return slow;1.3.3 debug debugging

Fast pointer moves to node [3], slow pointer moves to node [2]

Then take another step, the fast pointer moves to the node [5], and the slow node moves to the node [3], which meets the requirements of the topic.

Fourth, the last but one node in the linked list

1.4.1 topic analysis

The requirement of this problem is to return the countdown K nodes. The stupidest way is to reverse the list by referring to the list above. Get the first K nodes, and reverse the acquired nodes again to get the question requirements.

But obviously this way can only satisfy the answer output, after the above three questions, have you got any inspiration?

Yes, this problem can still be solved with double pointers. Does it feel like double pointers can solve all linked list problems (QAQ)?

If you think about it again, does it feel very similar to the title of "the middle node of the linked list"? The middle node to get the linked list is to return the second half of the node, while this question is required to return the specified K nodes.

Let's just come to the conclusion, which is also the pointer to define the speed. It's just that in the previous question, the fast pointer moves 2 nodes at a time, and the K given in this question is the number of nodes in which the fast pointer moves.

Also, the initialization pointer is on the first node, if we move the fast pointer to K nodes first.

At this point, the initialization node is complete, and all that remains is to traverse the remaining linked list until the fast pointer points to the last node.

Traverses until the fast node is null, which returns the node indicated by the slow pointer.

1.4.2 Code Analysis

Initialize the linked list, since the operation is the same as the previous questions, it is not shown here.

Gets the code for the penultimate node.

Public ListNode getKthFromEnd (ListNode head, int k) {ListNode slow = head; ListNode fast = head; / / move the fast pointer forward K while (Kmuri-> 0) {fast = fast.next;} while (fast! = null) {fast = fast.next; slow = slow.next;} return slow } 1.4.3 debug debugging

According to the above graphic analysis, the fast fast pointer to the node [3] is really initialized when the pointer is completed.

When the fast pointer points to node [5], the slow slow node points to node [3]

Note: one step is omitted in the middle, that is, when the slow pointer points to the node [2], the fast pointer points to the node [4].

Node [5] is the last node and enters the while loop again.

On the last loop, the slow pointer points to 4, and the next node of the fast pointer is null, ending the loop.

Fifth, remove duplicate nodes

1.5.1 topic analysis

This problem is the same as the title in the previous article, "remove repeating elements in the sorted list]. The simple way is to use the Set set to save the unduplicated nodes, and then go through the linked list to determine whether it already exists in the Set set.

Therefore, this question is not more analysis, just paste the code.

1.5.2 Code analysis Set set = new HashSet (); ListNode temp = head; while (temp! = null & & temp.next! = null) {set.add (temp.val); if (set.contains (temp.next.val)) {temp.next = temp.next.next;} else {temp = temp.next }} return head;} Thank you for your reading, the above is the content of "how to debug with debug". After the study of this article, I believe you have a deeper understanding of how to debug with debug, and the specific use needs to be verified in 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.