Topic describes

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.

solution

Define the fast and slow Pointers, slow and fast, which initially point to head.

If fast moves k steps forward, then slow and FAST move forward at the same time. When FAST points to null, the node pointed by slow is the KTH node from the end of the linked list.

Python3

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        slow = fast = head
        for _ in range(k):
            fast = fast.next
        while fast:
            slow = slow.next
            fast = fast.next
        return slow
Copy the code

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode slow = head, fast = head;
        while (k-- > 0) {
            fast = fast.next;
        }
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}
Copy the code

JavaScript

/** * @param {ListNode} head * @param {number} k * @return {ListNode} */ var getKthFromEnd = function (head, // function func(node) {// if(! node || ! node.next) return node // let newNode = func(node.next) // if(cnt === k) return newNode // else cnt++ // return node // } // return func(head) let slow = head; let fast = head; while (k) { fast = fast.next; k--; } while (fast) { slow = slow.next; fast = fast.next; } return slow; };Copy the code

C++

class Solution { public: ListNode* getKthFromEnd(ListNode* head, int k) { ListNode *slow = head, *fast = head; while (k--) { fast = fast->next; } while (fast) { slow = slow->next; fast = fast->next; } return slow; }};Copy the code