• Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

22. The k last node in the linked list

  • Input a linked list, output the last KTH node of the list. In keeping with the habits of most people,

    • In this case, 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.Copy the code

Methods 1 and 2 are the thoughts of the fast and slow Pointers

  • Ideas:
    • Let the fast pointer go firstkstep
    • Then the slow hand starts to move
    • When the fast pointer goes to the tail, the slow pointer goes exactly to the first inversekA node

Methods a

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;

        while(fast ! =null) {
            fast = fast.next;
            if (k == 0) {
                head = head.next;
            } else{ k--; }}returnhead; }}Copy the code

Method 2

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        ListNode low = head;

        for(int i=0; i<k; i++){
            fast = fast.next;
        }
        while(fast != null){
            fast = fast.next;
            low = low.next;
        }
        return low;
    }
}
Copy the code

conclusion

  • Although this problem is a very simple fast or slow pointer problem
    • But mastering the mind is the main thing
    • For example, when we’re doing other problems,
    • Such asCircular linked list,The common node of a linked list,Find the entry to the listEtc.
    • These are all questions about the fast or slow pointer, when you’re using the fast or slow pointer
    • Be careful whether you want to return the current node or a dummy nodenextnode