目录
1.题目
2.分析
思路
代码
提交结果
1.题目
面试题 02.02. 返回倒数第 k 个节点
实现一种算法,找出单向链表中倒数第 k 个节点。返回该节点的值。
注意:本题相对原题稍作改动
示例:
输入: 1->2->3->4->5 和 k = 2 输出: 4说明:
给定的 k 保证是有效的。
代码模板
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
int kthToLast(struct ListNode* head, int k)
{
}
2.分析
返回倒数第k个节点,由于不是双向链表,不能从尾节点向前遍历
倒数第k个节点即正数第(size-k+1)个节点,size为链表节点的总个数
思路
先遍历一次链表求size(while循环),之后不要忘记将遍历的指针恢复为head,再遍历一次得正数第(size-k+1)个节点(while循环)
代码
int kthToLast(struct ListNode* head, int k)
{int size=0;struct ListNode* cur=head;while(cur){cur=cur->next;size++;}cur=head;while(size-(k++))cur=cur->next;return cur->val;
}