面试题15-链表中倒数第k个结点

题目

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

解题

本题可以先遍历链表计数节点个数n，然后让指针从头开始移动n-(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) {
        // for robustness
        if (head == null || k == 0){
            return null;
        }
        ListNode node = head;
        int counter = 0;
        while (head != null){
            // for robustness
            if (head.next == null && counter<k-1){
                return null;
            }
            head = head.next;
            if (counter>k-1){
                node = node.next;
            }
            counter++;
        }
        return node;
    }
}

本题特别要注意的是代码的鲁棒性。可能的坑有三个：

1. 输入head为空；
2. k大于链表结点总数；
3. k =0。

总结

1. 注意找第k个结点，循环k-1次！对于这种边界条件不清楚的时候可以举简单的列子帮助自己清晰思路。
2. 灵活运用双指针。类似的题目还有：
   • 求链表的中间结点；
   • 判断一个单项链表是否形成了环形结构。

references

《剑指offer》