刷了有关链表的一些算法题后,我发现其中用到快慢指针的题不少,像中间节点,倒数第n个节点以及链表成环
链表成环问题我只前发过两篇博客详细的讲了一下
今天就来说一下另外两道题
题目链接
leecode链表的中间节点
https://leetcode.cn/problems/middle-of-the-linked-list/description/
牛客链表中倒数第k个节点
https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tab=note
首先这两道题都用到了快慢指针,而且及其相似,第一道题让慢指针走一步,快指针走两步,快指针走到空时,慢指针指向中间节点
第二道题同理,快指针先走k步,然后快慢指针一起走,快指针走向空,慢指针指向倒数第k个节点
下面分别是第一二道题的代码
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* middleNode(struct ListNode* head) { struct ListNode *slow, *fast; slow = fast = head; while(fast && fast->next) { fast = fast->next->next; slow = slow->next; } return slow; }
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * * @param pListHead ListNode类 * @param k int整型 * @return ListNode类 */ struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { // write code here struct ListNode* slow = pListHead, *fast = pListHead; if(k == 0) return NULL; while(fast) { if(k > 0) { fast = fast->next; k--; if(k == 1) { if(fast == NULL) return NULL; } } else { slow = slow->next; fast = fast->next; } } return slow; }
总结
关于这些问题,我们不难发现,在链表中快慢指针的应用相对频繁,在后续对链表的学习和对有关链表的算法题进行公克的时候,不妨多往快慢指针方面去想想
