数据结构-4、数据结构系列之如何查找单链表中倒数第N个节点

给定一个单链表，查找链表中倒数第n个节点

穷举遍历（两次遍历）

先遍历一遍链表，确定链表中节点的个数length。然后再遍历一遍链表，从前往后第（length-n+1）个节点就是倒数第n个节点。

public ListNode nthToLast(ListNode head,int n){
    ListNode first = head;
    int length = 0;
    while(first != null){
        length++;
        first = first.next;
    }
    first = head;
    for(int i = 0; i < length-n+1; i++){
        first = first.next;
    }
    return first;
}

双指针（一次遍历）

设置两个指针，第一个指针从头结点向前走到第n-1个节点时，第二个指针开始从头结点出发。当第一个指针走到尾结点时，第二个指针的位置即为倒数第n个节点。

public ListNode nthToLast(ListNode head,int n){
    ListNode first = head;
    ListNode second = head;
    for(int i = 0; i <= n-1; i++){
        //第一个指针开始遍历，保证输入的n值小于链表的长度
        first = first.next;
    }
    //第二个指针开始遍历
    while(first.next != null){
        first = first.next;
        second = second.next;
    }
    return second;
}