链表中快慢指针的应用

一枕眠秋雨

发布于 2024-03-11 18:13:13

720

发布于 2024-03-11 18:13:13

刷了有关链表的一些算法题后,我发现其中用到快慢指针的题不少,像中间节点,倒数第n个节点以及链表成环

链表成环问题我只前发过两篇博客详细的讲了一下

跳转链接 https://blog.csdn.net/lmy050813/article/details/136082903?utm_source=app&app_version=6.2.8&code=app_1562916241&uLinkId=usr1mkqgl919blen http://t.csdnimg.cn/e8p9P

今天就来说一下另外两道题

题目链接

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;
}