求链表中倒数第N个节点

发表于 分类于 ， ， Waline： 本文字数： 531 阅读时长 ≈ 1 分钟

思想

  • 定义两个指针a和b,
  • 指针b指向顺数第N个节点的位置
  • 然后指针a指向顺序第1个节点的位置
  • 同时把指针b和指针a向后平移
  • 当指针b指向最后一个节点时，此时的指针a指向的就是倒数第n个节点。

java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 求链表中的倒数第N个节点
 * 
 * @param head 链表的尾节点
 * @param n 要求倒数第几个节点
 * @return 倒数第n个节点的引用变量。
 */
public static Node findNFromLast(Node head, int n) {
    Node nthFromFirst = head;
    // 先求顺数第n个节点的
    for (int i = 0; i < n - 1; i++) {
        nthFromFirst = nthFromFirst.next;
    }
    // 顺数第一个节点
    Node first = head;
    // 把顺数第n个节点向后移动到尾节点，那么
    // 顺数第1个节点就是倒数的第n个节点
    while (nthFromFirst.next != null) {
        nthFromFirst = nthFromFirst.next;
        first = first.next;
    }
    return first;
}