本文主要是介绍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;
}
这篇关于CareerCup之2.2 寻找单链表倒数第n个元素的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
