美文网首页
输入一个链表,输出该链表中倒数第k 个结点

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

作者: 冉桓彬 | 来源:发表于2020-03-03 22:52 被阅读0次

输入一个链表,输出该链表中倒数第k 个结点。为了符合大多数人的习惯,本题从1 开始计数,即链表的尾结点是倒数第1 个结点.例如一个链表有6 个结点,从头结点开始它们的值依次是1 、2、3、4、5 、6。这个个链表的倒数第3 个结点是值为4 的结点。

需要注意边界问题

public class Node {
    public int value;
    public Node next;
}
pubic void test(Node head, int k) {
    if (head == null || k <= 0) {
        return null;
    }
    Node pointer = head;
    // 1. 将头节点移动到k位置.
    for (int i = 1; i < k; i++) {
        if (head.next != null) {
            // 每次移动结束后, 节点位置为i+1, 所以移动k-1次, 
            // 节点是被移动到k位置.
            head = head.next;
        } else {
            return null;
        }
    }
    // 2. 接下来pointer与header同时开始移动, header与pointer始终
    // 保持k-1的距离
    while (head.next != null) {
        head = head.next;
        pointer = pointer.next;
    }
    // 3. 移动结束, pointer节点为目标节点
    return pointer;
}

相关文章

网友评论

      本文标题:输入一个链表,输出该链表中倒数第k 个结点

      本文链接:https://www.haomeiwen.com/subject/dmzllhtx.html