The KTH last node in a linked list

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.

Java uses a fast full pointer. The fast pointer takes k-1 steps, then pQ goes together until the next fast pointer is empty, and returns the slow pointer. Python first gets the total length and then takes the length -1 step from the beginning based on the calculation.

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 p = head;
        ListNode q = head;

        for(int i =0; i<k- 1; i++){ p = p.next; }while(p.next! =null){ p = p.next; q = q.next; }returnq; }}Copy the code

python

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

class Solution(object):
    def getKthFromEnd(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        p = head
        math = 0
        while p :
            math = math + 1
            p = p.next
        for i in range(math-k):
            head = head.next
        return head
Copy the code