算法 输入一个链表，输出该链表中倒数第k个结点

输入一个链表，输出该链表中倒数第k个结点

 

题目：输入一个链表，输出该链表中倒数第k个结点

 

解法一：先递归到尾部，然后开始向前遍历，并计数，计数达到k时return

/*
public class ListNode {
    int val;
    ListNode next = null;
 
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    ListNode targetNode;
    int currK;
    public ListNode FindKthToTail(ListNode head, int k) { // 递归解法，比较渣
        if (k < 0 || head == null) {
            return null;
        }
        if (head.next != null) {
            FindKthToTail(head.next, k);
        } else {
            currK = k - 1;
        }
        if (currK-- == 0) {
            targetNode = head;
        }
        return targetNode;
    }
}

 

 

解法二：两个指针。第一个先正向移动到第K个节点（即移动k-1步），然后两个指针一起正向移动，当第一个指针到尾时，第二个指针指向的节点即为倒数第k个节点

 

/*
public class ListNode {
    int val;
    ListNode next = null;
 
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if (head == null || k <= 0) {
            return null;
        }
        ListNode first = head, second = head;
        for (int i = 0; i < k - 1; i++) {
            if (first == null) break;
            first = first.next;
        }
        if (first == null) { // happens when k > length
            return null;
        }
        while (first.next != null) {
            first = first.next;
            second = second.next;
        }
        return second;
    }
}