Aunt Guan is participating in the “Java Theme month – Java brush question clocking”, see the activity link for more details

First of all, I want to clarify that every algorithm problem has multiple solutions, and we’ll just talk about a few excellent solutions in LeetCode ~, hopefully

Can help you, that we first look at the topic description ~

I. Title Description:

Input a linked list, output the last KTH node of the list. In order to conform to the convention of most people, this case counts from 1, i.e. the last node of the list is the last node from the last. For example, a linked list has six nodes, starting with the head node, whose values are 1, 2, 3, 4, 5, and 6. The third from last node of the list is the node with the value 4.

Example: Given a linked list: 1->2->3->4->5, and k = 2. Return to list 4->5.

Ii. Analysis of Ideas:

If I knew the length of the list, I’d be able to figure out which node is the KTH, and then I’d iterate over the output. No. But we know that the length of the list requires that we first traverse the entire list, get the length of the list, and then iterate through the list to k, and then we can output it; But isn’t it a little bit of a hassle to iterate through the entire list? Is there a way to iterate through the entire list that doesn’t require it? We define two Pointers, called front and back Pointers, to point to the head node at the same time, and then let the front pointer take k steps first. At this point, the front and back Pointers are separated by k. If the current pointer moves forward, the next pointer points to the KTH node

Third, code demonstration

public ListNode getKthFromEnd(ListNode head, int k) { ListNode former = head, latter = head; for(int i = 0; i < k; i++){ former = former.next; } while(former ! = null) { former = former.next; latter = latter.next; } return latter; }Copy the code

Brush question summary

If you have other ideas to solve the problem, as long as you can achieve the requirements, it is no problem, all roads lead to Rome, not just limited to the solution I said ha ~, excellent ideas and code is more learning significance, let’s work together