假设该链表只给出了头指针head，在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第

假设该链表只给出了头指针head，在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data值，并返回1；否则，只返回0

很好做的，定义2个指针，一开始都指向head
第一个指针从head往后移动k个结点，另一个不动

第k个节点开始，两个指针同时向后移动，当第一个结点到达链表尾部的时候，另一个指针指向的便是倒数第k个结点。

typedef struct LNode { int data; struct LNode *next; }LNode; int LocateElement（LNode *head, int k） { LNode *p1 = head->next; LNode *p = head; int i = 1; while(p1) { p1 = p1->next; i++; if(i > k) p = p->next; } if(p == head) return 0; else { cout<data; return 1; } }

百万专业人才，在线为你服务，请查看我空间免费注册。