链表中倒数最后k个结点

方法1 寄存初始节点

用p寄存初始节点 然后用while算出pHead长度,直接用p前进n-k到需要返回的节点。

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param pHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode* FindKthToTail(struct ListNode* pHead, int k ) {
    // write code here
    int n = 1;
    struct ListNode* p = pHead;
    //检查初始节点是否为空
    if(pHead != NULL)while(pHead->next != NULL){
        n++;
        pHead = pHead->next;
    }
    if(n < k)return p = NULL;

    else {
        for(int i = 0; i < n-k; i++){
            p = p->next;
        }
    return p;
    }
}

方法2 双指针法

链表中倒数最后k个结点

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param pHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode* FindKthToTail(struct ListNode* pHead, int k ) {
    // write code here
   if (pHead == NULL)
            return NULL;
    struct ListNode* first = pHead;
    struct ListNode* second = pHead;
    //第一个指针先走k步
    while (k-- > 0) {
        if (first == NULL)
            return NULL;
        first = first->next;
    }
    //然后两个指针在同时前进
    while (first != NULL) {
        first = first->next;
        second = second->next;
    }
    return second;
}
上一篇:反转链表


下一篇:单链表详解(文末含有经过完整测试的全部代码~需要可自取)