欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LC_面试题 02.02. 返回倒数第 k 个节点

程序员文章站 2024-03-04 10:47:05
...

LC_面试题 02.02. 返回倒数第 k 个节点

解题思路

法一_双指针

  • 定义两个指针指向head
  • 将第一个指针做循环不断指向下一位,直至循环次数为k次
  • 将两个指针同步做循环不断指向下一位,直至第一个指针为空
  • 返回第二个指针所指向的值

法二_单指针(运行时间较短)

  • 定义一个指针temp = head,一个常数count = 0
  • 第一次用head遍历节点数时不断令count++,统计节点个数
  • 第二次用temp遍历节点数,做(count-k+1)次循环
  • 返回temp指向的值

提示

  • 注意循环的次数

代码

法一_双指针

class Solution {
public:
    int kthToLast(ListNode* head, int k) {
        ListNode* first = head;
        ListNode* second = head;
        for(int i=0;i<k;i++)
        {
            first = first->next;
        }
        while(first!=NULL)
        {
            first = first->next;
            second = second->next;
        }
        return second->val;
    }
};

法二_单指针

class Solution {
public:
    int kthToLast(ListNode* head, int k) {
        ListNode* temp = head;
        int count = 0;
        while(head->next!=NULL)
        {
            count++;
            head = head->next;
        }
        for(int i=0;i<count-k+1;i++)
        {
            temp = temp->next;
        }
        return temp->val;
    }
};
相关标签: LC