剑指Offer——链表中倒数第k个结点

By AverageJoeWang
 标签:

链表中倒数第k个结点

  • 题目描述
    输入一个链表,输出该链表中倒数第k个结点。

  • 解题思路

    • 先看看所给链表是不是为空,然后检查k是否为负数或者为0
    • 利用2个指针,第一个指针先走k步,走的过程中需要检查第一个指针所指是否为空
    • 待第一个指针走k步以后,第二个指针从头开始走
    • 第一个第二个指针一起走,直到第二个指针的的下一个节点为null,返回第二个指针就是所指的倒数第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;
        ListNode second = head;
        for (int i = 1; i < k; i++){
            if (first.next != null){
                first = first.next;
            }else {
                return null;
            }
        }
        while (first.next != null){
            first = first.next;
            second = second.next;
        }
        return second;
    }
}