本文共 1588 字，大约阅读时间需要 5 分钟。

面试题22：链表中倒数第k个节点

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

思路：

1. 定义两个指针，其中第一个指针先指向第3个节点。另一个指针指向第一个节点
2. 两个指针同时后移，当后一个指针到达链表尾部时，前一个指针指向的就是倒数第3个节点。

代码实现：

package Question22;public class T01 {       public static void main(String[] args) {           Node node1 = new Node(1);        Node node2 = new Node(2);        Node node3 = new Node(3);        Node node4 = new Node(4);        Node node5 = new Node(5);        Node node6 = new Node(6);        node1.next = node2;        node2.next = node3;        node3.next = node4;        node4.next = node5;        node5.next = node6;        System.out.println(solve(node1, 3));    }    public static Node solve(Node head, int k) {           if(head == null || k == 0) return null;        Node pre = head, post = head;        while(k-1 > 0) {               post = post.next;            if(post == null) return null;            k--;        }        while(post.next != null) {               pre = pre.next;            post = post.next;        }        return pre;    }}class Node{       public int id;    public Node next;    public Node(int id) {           this.id = id;    }    @Override    public String toString() {           return "Node{" +                "id=" + id +                '}';    }}

注意：这题比较简单，但是一定注意注意代码的鲁棒性，及输入和合法性、程序过程的正确性等。

相关题目

求链表的中间节点。如果链表中的节点总数为奇数，则返回中间节点；如果节点总数为偶数，则返回中间两个节点的任意一个。为了解决这个问题，我们也可以定义两个指针，同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。当走得快的指针走到链表的末尾时，走得慢的指针正好在链表的中间。

举一反三

当我们用一个指针遍历链表不能解决问题的时候，可以尝试用两个指针来遍历链表。可以让其中一个指针遍历的速度快一些（比如一次在链表上走两步），或者让它先走几步。