---

算法设计思想

1. 快慢指针法核心思路

• 使用两个指针（快指针和慢指针）以不同的速度遍历链表

• 通过控制两个指针的移动步数差，实现特定位置的定位

2. 查找倒数第k个结点的具体策略

   建立k步距离：让快指针先移动k步，建立与慢指针的固定间隔

   同步移动：然后两个指针同步移动，保持这个间隔

   终止条件：当快指针到达链表末尾时，慢指针正好指向倒数第k个结点

// 链表结构体定义
typedef struct LNode{
    int data;
    struct LNode* link;
}LNode, *LinkList;

 

int func(LinkList head, int k){
    if (head == NULL || k <= 0) return 0;  // 非法输入处理
    LNode *fast = head->link, *slow = head;  // fast从首结点开始，slow保留头结点
    for(int i=1; i<=k && fast!=NULL; i++){
        fast = fast->next;
    }
    while(fast != NULL){
        fast = fast->next;
        slow = slow->next;
    }
    if(slow == head) return 0;
    else{
        printf("%d", slow->data);
        return 1;
    }
}

时间复杂度与空间复杂度分析

1. 时间复杂度

   最优情况：O(n)，无论k值大小，算法都只需要遍历链表一次 最坏情况：O(n)，即使k=1或k=n，也只需要一次完整遍历 平均情况：O(n)，与链表长度线性相关

2. 空间复杂度 固定空间：O(1)，仅使用两个额外指针变量（fast和slow） 无递归栈：不使用递归，避免栈空间开销

---