JZ22-题解 | #链表中倒数最后k个结点#

链表中倒数最后k个结点

http://www.nowcoder.com/practice/886370fe658f41b498d40fb34ae76ff9

题目描述

输入一个长度为 n 的链表,设链表中的元素的值为 ai ,返回该链表中倒数第k个节点。 如果该链表长度小于k,请返回一个长度为 0 的链表。


**题解1:使用双指针,fast指向第k个节点,slow指向第一个节点 //此时,fast后面的节点个数为链表长度-k,

/**
* struct ListNode {
*	int val;
*	struct ListNode *next;
*	ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
   /**
    * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
    *
    * 
    * @param pHead ListNode类 
    * @param k int整型 
    * @return ListNode类
    */
   ListNode* FindKthToTail(ListNode* pHead, int k) {
       // write code here
       ListNode * fast = pHead,*slow = pHead;
       for(int i=0;i<k;i++){//fast先指向第k个结点
           if(fast ==NULL)
               return NULL;
           fast = fast->next;
       }
       while(fast){//一直循环,直到fast指向最尾端。
           fast = fast->next;
           slow = slow->next;//slow和fast仪器运动
       }
       return slow;
   }
};

题解2:使用辅助数组

ListNode* FindKthToTail(ListNode* pHead, int k) {
    vector<ListNode*> v;
    ListNode* temp = pHead;
    while (temp) {
        v.push_back(temp);
        temp = temp->next;
    }
    if (v.size() < k)
        return NULL;
    return v[v.size() - k];
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-23 14:10
码农索隆:成年人最直白的答复:已读不回
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-24 12:26
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务