521
技術社區[雲棲]
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;
}
最後更新：2017-04-03 12:56:43