CareerCup之2.2 寻找单链表倒数第n个元素

【题目】

原文：

2.2 Implement an algorithm to find the nth to last element of a singly linked list.

译文：

实现一个算法从一个单链表中返回倒数第n个元素。

【分析】

（1）创建两个指针p1和p2,指向单链表的开始节点。

（2）使p2移动n-1个位置，使之指向从头开始的第n个节点。（意思是就是使p1和p2距离n个位置）

（3）接下来检查p2 - > = = null 如果yes返回p1的值,否则继续移动p1和 p2如果接下来p2为null意味着p1指向从结尾开始计算的第n个节点。

（4）重复第三步

【代码】

/*********************************
*   日期：2014-5-18
*   作者：SJF0115
*   题目: 寻找单链表倒数第n个元素
*   来源：CareerCup
**********************************/
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* nthToLast(ListNode* head,int n){
    //head 带有头结点的单链表
    if(head->next == NULL || head == NULL || n <= 0){
        return NULL;
    }
    int i;
    ListNode* p1 = head->next;
    ListNode* p2 = head->next;
    //p2移动n-1个位置
    for(i = 1;i <= n-1;i++){
        //总共元素不到n个
        if(p2 == NULL){
            return NULL;
        }
        p2 = p2->next;
    }
    //p2移动至末尾则p1移动到倒数第n个元素
    while(p2->next != NULL){
        p1 = p1->next;
        p2 = p2->next;
    }
    return p1;
}

int main(){
    int i,j;
    //freopen("C:\\Users\\XIAOSI\\Desktop\\acm.txt","r",stdin);
    ListNode *head = (ListNode*)malloc(sizeof(ListNode));
    head->next = NULL;
    ListNode *node;
    ListNode *pre = head;

    int A[] = {6,5,3,3,6,5,6,7,3,7,1,2,1,4,6,7,2,3};

    for(int i = 0;i < 18;i++){
        node = (ListNode*)malloc(sizeof(ListNode));
        node->val = A[i];
        node->next = NULL;
        pre->next = node;
        pre = node;
    }

    node = nthToLast(head,18);
    if(node != NULL){
        cout<<node->val<<endl;
    }
    else{
        cout<<""<<endl;
    }
    return 0;
}