网站建设所需的软件,邯郸自媒体有哪些,苍溪县规划和建设局网站,o2o网站建设公司1 问题
打印链表的倒数第N个节点的值#xff0c;#xff08;要求能只能便利链表一次#xff09;
比如链表如下#xff0c;打印倒数第三个值就是4
1- 2- 3- 4- 5- 6 2 思路
既然只要只能遍历一次#xff0c;我们可以这样思考#xff0c;比如我们要…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 iostreamusing 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 5 总结
请记住2个指针像一把梭子那样在移动是那么的美妙所以当一个指针便利不了的时候要记得用2个指针便利
然后还有类似的问题比如求链表的中点链表长度是奇数的时候取中间的数字如果链表长度是偶数的话取中间的2个都行我们依然用2个指针一个走一步一个走2步当快的走完了的时候慢的的走到中间了切记。
