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

程序员文章站 2024-03-04 09:41:47

...

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

自己解

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int kthToLast(ListNode* head, int k) {
        if(k < 0)
            return -1;
        if(head == NULL)
            return -1;
        int count = 0;
        ListNode* fast = head;
        ListNode* low = NULL;
        while(fast)
        {
            count++;
            if(count == k)
                low = head;
            else if(count > k)
                low = low->next;
            fast = fast->next;
        }
        return low->val;
    }
};