每日一题 Leetcode 面试题02.02

两种解法

1.直接解法

先创建一个新的指针*p用于存放head，用p来求单链表长度，然后根据长度和给定k的值判断所求为正向第n个元素，循环n-1次找到对应值即可

/**
 * 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) {
        
        //新建指针
        ListNode* p;
        p=head;
        //单链表长度
        int len=0;
        //所求值
        int n=0;
 
        //遍历单链表，求链表长度
        while(p!=NULL)
        {
            len++;  
            p=p->next;
        }
 
        //根据长度和给定k求所求值
        for(int i=0;i<len-k+1;i++)
        {
            n=head->val;
            head=head->next;
        }
 
        return n; 
 
 
    }
};
 
作者：kutu1bw-i
链接：https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/solution/bao-li-jie-fa-by-kutu1bw-i-4ehf/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2.双指针法

先创建两个指针（这里指左、右），先基于给定k，将右指针向右移动k-1次，使左指针与右指针相距为k-1，在同时移动左、右指针，当右指针到达链表底部时，所求即为左指针对应的值

/**
 * 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) {
 
        ListNode* p;
        p=head;
        // int len=0;
        // int n=0;
 
        while(k--)
        {  
            p=p->next;
        }
 
        while(p!=NULL)
        {
            p=p->next;
            head=head->next;
        }
 
        return head->val; 
 
 
    }
};