坚持看完，结尾有思维导图总结

快慢指针在链表中的运用

• 链表的中间结点
• • 步骤
  • 例子分析
  • • 奇数情况
    • 偶数情况
  • 程序
• 链表中倒数第k个结点
• • 步骤
  • 解析
  • 程序

链表的中间结点

leetcode 链接

步骤

1. 设置两个指针来遍历链表，一个叫 fast 每次跳过两个元素，一个叫 slow 每次跳过一个元素
2. 当 fast 跳到尾的时候，slow 正好是中间节点

例子分析

奇数情况

奇数的时候，跳到最后一个节点

偶数情况

偶数时，跳到 NULL节点

程序

#include
struct ListNode* middleNode(struct ListNode* head){struct ListNode* fast = head;struct ListNode* slow = head;if(fast==NULL){return NULL;}//保证能够向后跳while(fast != NULL &&fast->next != NULL ){fast = fast->next->next;slow = slow->next;}return slow;}

注意要判断 fast 退出的判断

链表中倒数第k个结点

牛客网链接

步骤

1. 设置两个指针 一个指针叫 front 先走 k 步
2. front 走完 k 步 后 再开始走
3. 当front 走到尾的时候 ，slow 恰好指向倒是第k个节点

解析

程序

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode* front = pListHead;struct ListNode* after = pListHead;//先走 k 步while(k){if(front == NULL){return NULL;}front = front->next;k--;}//slow 跟上while(front){front = front->next;after = after->next;}return after;
}

注意 : front 在k步内走完链表的可能

希望大家看完，能够有所收获
如果有错误，请指出我一定虚心改正
动动小手点赞
鼓励我输出更加优质的内容