1 问题
打印链表的倒数第N个节点的值，（要求能只能便利链表一次）
比如链表如下，打印倒数第三个值就是4
1-> 2-> 3-> 4-> 5-> 6
2 思路
既然只要只能遍历一次，我们可以这样思考，比如我们要得到倒数第三个，那么它和尾巴的长度就是3，我们可以这一节距离一直往左边移动，那么移动最左边的话，他们的开始是1，尾巴是3，所以我们搞2个指针进行移动就行，如下过程，就可以得到4.
1 -> 2 -> 3 -> 4 -> 5 -> 6
start
end
1 -> 2 -> 3 -> 4 -> 5 -> 6
start end
1 -> 2 -> 3 -> 4 -> 5 -> 6
start end
无非就是上面的逆过程，我们用代码实现就行
3 代码实现
#include <iostream> using namespace std; typedef struct node { int value; struct node *next; } Node; void printN(Node *head, int n) { if (head == NULL || n <= 0) { std::cout << "head is NULL or n <= 0" << std::endl; return; } Node *start = head; Node *end = head; //这里需要考虑n的大小长度是否大于链表长度 //我们不能直接遍历链表得到链表大小然后和n比较 //那我们就用start->next != NULL来判断也行 for (int i = 0; i < n - 1; ++i) { if (start->next != NULL) start = start->next; else { std::cout << "the value of n is more than larger the length of list" << std::endl; return; } } while (start->next != NULL) { end = end->next; start = start->next; } std::cout << "the value is: " << end->value << std::endl; } int main() { Node *head = NULL; Node *node1 = NULL; Node *node2 = NULL; Node *node3 = NULL; head = (struct node*)malloc(sizeof(Node)); node1 = (struct node*)malloc(sizeof(Node)); node2 = (struct node*)malloc(sizeof(Node)); node3 = (struct node*)malloc(sizeof(Node)); if (head == NULL || node1 == NULL || node2 == NULL || node3 == NULL) { std::cout << "malloc fail" << std::endl; return -1; } head->value = 0; head->next = node1; node1->value = 1; node1->next = node2; node2->value = 2; node2->next = node3; node3->value = 3; node3->next = NULL; printN(head, 3); free(head); free(node1); free(node2); free(node3); return 0; }
4 运行结果
the value is: 1
