剑指Offer刷题笔记（Java）14——链表中倒数第k个结点

题目描述

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

解题思路

记录每个节点内容

这是最简单最直观的方法，因为链表无法记录每个节点的位置，因此遍历该链表记录每个节点的位置并保存当前节点，当输入k时，根据已经保存的位置就可以找到对应位置的节点。这里有一些边界条件需要判断，首先是链表为空的时候，直接输出null；如果链表的长度小于k值或k为0或负数，则也要输出null。具体代码如下：

import java.util.ArrayList;
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head == null){
            return null;
        }
        ArrayList<ListNode> list = new ArrayList<>();
        int count = 0;
        while(head != null){
            list.add(head);
            count++;
            head = head.next;
        }
        if(k > count || k <= 0){
            return null;
        }
        int num = count - k;
        return list.get(num);
    }
}

利用两个指针

这是书上的想法，我觉得想法应该被借鉴。假设共有n各节点，倒数第k个节点和最后一个节点之间相差k-1，设置两个指针，让它们之间始终相差k-1，同时向后遍历，当前面节点走都最后时，就可以找到对应的节点了。因此这种方法要首先判断后面的指针什么时候开始遍历，前面的指针走到k-1处时后面的指针开始往后走，而前面的指针接着往后走就可以，这样就只需要遍历一次链表。具体代码如下：

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head == null || k<=0){
            return null;
        }
        ListNode newNode = head;
        ListNode curNode = head;
        for(int i=0;i<k-1;i++){
            if(curNode.next != null){
                curNode=curNode.next;
            }else{
                return null;
            }
        }
        while(curNode.next != null){
            curNode = curNode.next;
            newNode = newNode.next;
        }
        return newNode;
    }
}

这种解法最关键的地方还是在边界条件的判断，链表为空的时候，直接输出null；如果链表的长度小于k值或k为0或负数，则也要输出null。

总结

针对链表问题，要活用指针，很多情况下要用到两个指针，要搞清楚两个指针之间的关系，有思路之后解题就容易多了。