2020-04-06:链表中倒数第k个节点

链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

来源：力扣（LeetCode）

题解

• 方法一:常规方法

首先想到的方法是先循环遍历得到链表的长度n，然后再循环n-k次获得倒数第k个节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* getKthFromEnd(struct ListNode* head, int k){
    int len=0;
    struct ListNode *ptr = head;
    while(ptr)
    {
        len++;
        ptr=ptr->next;
    }
    int j=len-k;
    while(head && j>0)
    {
        j--;
        head=head->next;
    }
    return head;
}

• 方法二：双指针

倒数第k个节点，可以理解成距离最后一个节点（这里可以认为是NULL）隔了k个节点。
所以可以用两个相隔k个节点的指针同步移动，当前面的指针移动到尾部时，后面的指针
刚好到距离前面指针k个节点的位置。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* getKthFromEnd(struct ListNode* head, int k){
    struct ListNode *former=head;
    struct ListNode *latter=head;
    while(former!=NULL)
    {
        former=former->next;
        if(k>0){
            k--;
        }else{
            latter=latter->next;
        }
    }
    return latter;
}