程序员代码面试指南2.2：在链表中删除倒数第K个节点

1、思路

书中描述的方法稍显复杂，这里用一种更简单的思路：

• 快慢指针指向头结点，快指针先往前移动K步；

• 若快指针遍历完链表后，K大于0，表示K的值已经超过了链表本身的长度，即不存在倒数第K个节点；

• 快慢指针同时往前走，快指针走到链表尾部时，慢指针所指的就是倒数第K个节点。因为慢指针比快指针少走了K步，故快指针走完链表时，慢指针刚好走到链表的倒数第K个节点。

2、代码

list_node * remove_last_kth_node(list_node * head, int K)
{
    auto fast = head, slow = head;

    while (K --  && fast->next != nullptr) fast = fast->next;
    if (K > 0) return nullptr;      //判断倒数第K个节点是否存在

    while (fast->next != nullptr)
    {
        fast = fast->next;
        slow = slow->next;
    }

    slow->next = slow->next->next;  //跳过倒数第K个节点

    return head;
}