数据结构与算法 - 实战：查找链表中倒数第n个结点

题目：查找链表中倒数第n个结点

解析：这个题目有三种解法，分别如下

方法一：根据位置获取单链表中倒数第n个结点

假设单链表总共length个结点，倒数第n个就等于链表正着数的第（length-n+1）个结点
注：getNodeByPosition（ListNode headNode， int position）参见上一篇博客单链表的操作


/**
 * 找到链表中倒数第n个结点
 * @param n 倒数结点位置
 * @return 倒数第n个结点
 */
public static ListNode getReciprocalNode1(ListNode headNode, int n) {
    // 先获取链表长度，判断n是否小于等于0
    int length = getLength(headNode);
    if (n < 1) {
        System.out.println("结点的个数不能为小于1");
        return null;
    }
    // 判断链表个数是否够n个
    if (n > length) {
        System.out.println("链表中结点的个数不足" + n + "个");
        return null;
    }

    /*
     * 方法一：根据位置获取倒数第n个结点
     * 总共length个结点，倒数第n个就等于正着数的（length-n+1）个结点
     */
    ListNode currentNode = getNodeByPosition(headNode, length - n + 1);
    return currentNode;
}

方法二：每次都从当前结点扫描链表中剩余的结点个数

这里采用一个笨的方法，从第一个开始一个一个判断，每次都从当前结点扫描链表中剩余的结点个数

/**
 * 找到链表中倒数第n个结点
 * @param n 倒数结点位置
 * @return 倒数第n个结点
 */
public static ListNode getReciprocalNode2(ListNode headNode, int n) {
    // 先获取链表长度，判断n是否小于等于0
    int length = getLength(headNode);
    if (n < 1) {
        System.out.println("结点的个数不能为小于1");
        return null;
    }
    // 判断链表个数是否够n个
    if (n > length) {
        System.out.println("链表中结点的个数不足" + n + "个");
        return null;
    }

    /*  
     * 方法二：每次都从当前结点扫描链表中剩余的结点个数 
     * 这里采用一个笨的方法，从第一个开始一个一个判断，每次都从当前结点扫描链表中剩余的结点个数
     */
    ListNode currentNode = headNode;
    while(length > n) {
        currentNode = currentNode.getNext();
        length--;
    }
    return currentNode;
}

方法三：

使用两个指针pTemp和pNth。首先，两个指针都指向链表的头结点。
先使pTemp移动n次后，pNth才开始移动。此时两个指针一起移动，
当pTemp指针移动到链表的尾部，也就是pTemp指向链表的最后一个结点。
此时pNth所指向的结点就是所要求的倒数第n个结点。

/**
 * 找到链表中倒数第n个结点
 * @param n 倒数结点位置
 * @return 倒数第n个结点
 */
public static ListNode getReciprocalNode3(ListNode headNode, int n) {
    // 先获取链表长度，判断n是否小于等于0
    int length = getLength(headNode);
    if (n < 1) {
        System.out.println("结点的个数不能为小于1");
        return null;
    }
    // 判断链表个数是否够n个
    if (n > length) {
        System.out.println("链表中结点的个数不足" + n + "个");
        return null;
    }

    /*
     * 方法三：
     * 使用两个指针pTemp和pNth。首先，两个指针都指向链表的头结点。
     * 先使pTemp移动n次后，pNth才开始移动。此时两个指针一起移动，
     * 当pTemp指针移动到链表的尾部，也就是pTemp指向链表的最后一个结点。
     * 此时pNth所指向的结点就是所要求的倒数第n个结点。
     */
    ListNode pTemp = headNode;
    ListNode pNth = headNode;
    // 使pTemp移动n次
    for (int i = 0; i < n; i++) {
        if (pTemp != null) {
            pTemp = pTemp.getNext();
        }
    }
    // pTemp和pNth两个指针一起移动
    while (pTemp != null) {
        pTemp = pTemp.getNext();
        pNth = pNth.getNext();
    }
    // 返回结果
    return pNth;
}

目前为止，方法三是一个很有效的解决方案。

04、数据结构与算法 - 实战：查找链表中倒数第n个结点