【算法】链表中倒数第k个结点——递归解法

版权声明：本文为博主原创文章，转载请注明出处：https://twocups.cn/index.php/2020/01/16/13/

最近我遇到“链表中倒数第k个结点”这道算法题，做完后发现大家用的都是双指针解法，没有人用递归解法做。不过递归用到了栈，所以空间复杂度就不是 O(1) 了。但这里不讨论算法的优劣，我只是觉得用递归思想解这题很有意思，所以和大家分享一下递归解法。

题目描述

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

链表结构

public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}

双指针解法

public ListNode FindKthToTail(ListNode head,int k) {
    ListNode first,last;
    first = last = head;
    int i = 0;
    for(;last != null;i++){
        if(i>=k)
            first = first.next;
        last = last.next;
    }
    return i < k ? null :first;
}

递归解法

int count = 1;
ListNode node;
public ListNode FindKthToTail(ListNode head,int k) {
    if(head != null){
        this.FindKthToTail(head.next,k);
        if(count++ == k){
            node = head;
        }
    }
    return node;
}