166. 链表倒数第n个节点

166. 链表倒数第n个节点

• 描述
• 笔记
• 数据
• 评测

找到单链表倒数第n个节点，保证链表中节点的最少数量为n。

您在真实的面试中是否遇到过这个题？

Yes

样例

给出链表 3->2->1->5->null和n = 2，返回倒数第二个节点的值1.

标签
思路：
此题有两种解法：
1.遍历两次链表，先遍历第一次记录总的节点个数，再遍历第二次sum-n+1可求得倒数第n个节点个数
AC代码：

class Solution {
public:
    /*
     * @param head: The first node of linked list.
     * @param n: An integer
     * @return: Nth to last node of a singly linked list. 
     */
    ListNode * nthToLast(ListNode * head, int n) {
        // write your code here
        ListNode *p;
        int sum=0;
        if ( head == NULL || n == 0 ) {  
            return NULL;  
        } 
        p=head;
         while (p -> next != NULL) {  
            p = p -> next;  
            sum++;  
        }  
        int m=sum-n+1;
        p=head;
        while(m--){
            p=p->next;
        }
        return p;
    }
};

2.遍历一次链表，设两个节点，先用第一个遍历至第n-1个节点，然后设一个循环，第二个从head开始出遍历，第一个从n-1处遍历，当第一个遍历到链表尾时，第二个也就遍历到倒数第n个了。
AC代码：

class Solution {  
public:  
    /** 
     * @param head: The first node of linked list. 
     * @param n: An integer. 
     * @return: Nth to last node of a singly linked list.  
     */  
    ListNode *nthToLast(ListNode *head, int n) {  
        // write your code here  
        ListNode *p1 , *p2;  
        // 边界条件，如果链表为空，或者输入的数字非正，返回空  
        if ( head == NULL || n <= 0 ) {  
            return NULL;  
        }  
        p1 = head;  
        for ( int i = 0; i < n-1 ; i++ ) {  
        // 第一个指针开始遍历，保证输入的n值小于链表的长度，否则返回空  
            if ( p1 -> next != NULL ) {  
                p1 = p1 -> next;  
            } else {  
                return NULL;  
            }  
        }  
        p2 = head; // 第二个指针开始遍历  
        while ( p1 ->next != NULL ) {  
            p1 = p1 ->next;  
            p2 = p2 ->next;  
        }  
        return p2;  
    }  
};