给定一个链表和一个数字n，返回该链表的倒数第n个节点的值。

比如，当输入如下且n=3，则输出为“B”

g

方法1

1）计算链表的长度len
2） 打印从链表开头起的第（len – n + 1）个节点

代码如下

class LinkedList { 
    Node head; // head of the list 
  
    /* Linked List node */
    class Node { 
        int data; 
        Node next; 
        Node(int d) 
        { 
            data = d; 
            next = null; 
        } 
    } 
  
    /* 打印链表的倒数第n个节点 */
    void printNthFromLast(int n) 
    { 
        int len = 0; 
        Node temp = head; 
  
        // 1) 结算链表节点数 
        while (temp != null) { 
            temp = temp.next; 
            len++; 
        } 
 
        if (len < n) 
            return; 
  
        temp = head; 
  
        // 2) 获取从链表头开始的第 (len-n+1)个节点 
        for (int i = 1; i < len - n + 1; i++) 
            temp = temp.next; 
  
        System.out.println(temp.data); 
    } 
  
    /* 添加新节点到链表头 */
    public void push(int new_data) 
    { 
        /* 1 & 2:生成新节点 */
        Node new_node = new Node(new_data); 
  
        /* 3. 将新节点的next指向head */
        new_node.next = head; 
  
        /* 4. 将head指向新节点 */
        head = new_node; 
    } 
  
    /*驱动测试函数 */
    public static void main(String[] args) 
    { 
        LinkedList llist = new LinkedList(); 
        llist.push(20); 
        llist.push(4); 
        llist.push(15); 
        llist.push(35); 
  
        llist.printNthFromLast(4); 
    } 
} 

输出：

35 

以下是相同方法的递归C代码。

void printNthFromLast(struct Node* head, int n) 
{ 
    static int i = 0; 
    if (head == NULL) 
        return; 
    printNthFromLast(head->next, n); 
    if (++i == n) 
        printf("%d", head->data); 
} 

时间复杂度： O（n），其中n是链表的长度。

方法2（使用两个指针）

维护两个指针–ref_Ptr和main_Ptr。初始化ref_Ptr和main_Ptr指向head节点。首先，将ref_Ptr从头移动n个节点。现在，将两个指针一一移动，直到ref_Ptr到达终点（为NULL）为止。现在，main_Ptr将从末尾算起指向第n个节点，返回main_Ptr即可。

class LinkedList { 
   Node head; // head of the list 
 
   /* Linked List node */
   class Node { 
       int data; 
       Node next; 
       Node(int d) 
       { 
           data = d; 
           next = null; 
       } 
   } 
 
   /* Function to get the nth node from end of list */
   void printNthFromLast(int n) 
   { 
       Node main_ptr = head; 
       Node ref_ptr = head; 
 
       int count = 0; 
       if (head != null) { 
           while (count < n) { 
               if (ref_ptr == null) { 
                   System.out.println(n + " is greater than the no "
                                      + " of nodes in the list"); 
                   return; 
               } 
               ref_ptr = ref_ptr.next; 
               count++; 
           } 
           while (ref_ptr != null) { 
               main_ptr = main_ptr.next; 
               ref_ptr = ref_ptr.next; 
           } 
           System.out.println("Node no. " + n + " from last is " + main_ptr.data); 
       } 
   } 
 
   /* Inserts a new Node at front of the list. */
   public void push(int new_data) 
   { 
       /* 1 & 2: Allocate the Node & 
                 Put in the data*/
       Node new_node = new Node(new_data); 
 
       /* 3. Make next of new Node as head */
       new_node.next = head; 
 
       /* 4. Move the head to point to new Node */
       head = new_node; 
   } 
 
   /*Drier program to test above methods */
   public static void main(String[] args) 
   { 
       LinkedList llist = new LinkedList(); 
       llist.push(20); 
       llist.push(4); 
       llist.push(15); 
       llist.push(35); 
 
       llist.printNthFromLast(4); 
   } 
} 

输出：

Node no. 4 from last is 35