14. “Finger Offer” — Find the KTH node from the bottom of a list

Topic:

Input a linked list, output the last KTH node of the list.

Ideas:

Use two Pointers, pre and tail, to move the two Pointers so that the distance between pre and tail is k-1. The linked list formed by the two nodes and the nodes between them is a “ruler” of length K +1. Move the ruler so that tail moves to the last node.

In addition, the main function needs to be written with the arrayToList() method to make the array a linked list.

Java

package nowcoder;

public class S14_FindKthToTail {
    public ListNode findKthToTail(ListNode head, int k) {
        ListNode pre = head;
        ListNode last = head;
        if(head==null || k <=0)
            return null;
        for(int i=0; i <k-1; I++){// make the spacing between pre and last k-1if(last.next! =null){ last = last.next; }else
                return null;
        }
        while(last.next! =null){// The space between pre and last is k-1, and last is moved to the last node. last = last.next; }return pre;
    }
    public ListNode arrayToList(int[] array, int index){
        ListNode head = null;
        if (index < array.length){
            int value = array[index];
            head = new ListNode(value);
            head.next = arrayToList(array, index+1);
        }
        return head;
    }
    public static void main(String[] args){
        S14_FindKthToTail s14 = new S14_FindKthToTail();
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8};
        ListNode head = s14.arrayToList(array, 0);
        ListNode result = s14.findKthToTail(head, 3);
        if (result == null)
            System.out.print("null");
        elseSystem.out.print(result.val); }}Copy the code

Python

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class FindKthToTail:
    def findKthToTail(self, head, k):
        tail = pre = head
        for _ in range(k):
            if not tail:
                return None
            tail = tail.next
        while tail:
            pre = pre.next
            tail = tail.next
        return pre
    def arrayToList(self, array, index):
        head = None
        if index < len(array):
            value = array[index]
            head = ListNode(value)
            head.next = self.arrayToList(array, index+1)
        return head

if __name__ == '__main__':
    test = FindKthToTail()
    array = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    head = test.arrayToList(array, 0)
    result = test.findKthToTail(head, 11)
    if result:
        print(result.val)
    else:print("null")
Copy the code