【leetcode】链表的中间节点|链表中倒数第k个节点-Toy模板网

这篇具有很好参考价值的文章主要介绍了【leetcode】链表的中间节点|链表中倒数第k个节点。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.链表的中间节点

2.链表中倒数第k个节点

1.链表的中间节点

【leetcode】链表的中间节点|链表中倒数第k个节点,数据结构,leetcode,链表,算法

思路1：遍历链表，统计节点个数count，返回第count/2 +1个节点

📖Note:注意循环条件为--mid，--mid循环执行mid-1次，mid--循环mid次，返回的是中间节点的下一个节点

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* cur = head;
    int count = 0;
    //统计节点个数
    while(cur)
    {
        count++;
        cur = cur->next;
    }
    //返回第count/2+1个节点
    cur = head;
    int mid = count/2 + 1;
    while(--mid)
    {
        cur = cur->next;
    }

    return cur;

}

思路二：快慢指针

设置一个慢指针slow，一个快指针fast，慢指针一次走一步，快指针一次走两步

需要分两种情况：链表节点个数为奇数个和节点个数为偶数个

1️⃣奇数个的情况

当链表节点个数为奇数个时，可以发现，快指针fast->next == NULL时，遍历结束，此时慢指针slow刚好指向中间节点

2️⃣偶数个的情况：

当链表节点个数为偶数个时，可以发现，快指针fast == NULL时，遍历结束，此时慢指针slow刚好指向中间节点

综上：遍历结束的条件为fast == NULL或fast->next == NULL

参考代码如下：文章来源地址https://www.toymoban.com/news/detail-610808.html

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* fast = head;
    struct ListNode* slow = head;

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

    return slow;

}

2.链表中倒数第k个节点

与上题思路二相似的还有下例

【leetcode】链表的中间节点|链表中倒数第k个节点,数据结构,leetcode,链表,算法

分析：

输出链表中倒数第k个节点，假设有一个指针指向链表尾节点的next，即指向NULL，我们从这个节点向前看，尾节点相对这个指针来说是第一个节点，相对链表头指针head来说便是倒数第一个节点，对于倒数第k个节点，指向这个节点的指针和指向NULL的指针始终相差的是k个节点；设置一个快指针fast，一个慢指针slow，fast指针先走k步，slow指针不动，此时fast指针和slow指针就相差k个节点，然后slow指针和fast指针同时向后走，直到fast指针指向NULL，此时slow指向的节点就是倒数第k个节点

以输出倒数第三个节点为例，步骤如下图：

🌸特殊情况讨论：

1️⃣空链表：返回空指针

2️⃣倒数第一个

由上图可以发现，输出倒数第一个节点的逻辑与输出倒数的k个节点的逻辑相同

3️⃣倒数第N个（链表长度为N）

由上图可以发现，输出倒数第N个节点的逻辑与输出倒数的k个节点的逻辑相同

4️⃣k=0或k>N（N为链表的长度）

k=0时，输出链表的倒数第0个节点，应该为空

此时fast指针和slow指针都不会发生变化，，所以

k>N时，fast先走k步会发生空指针的访问

在fast指针向后走k步的过程中，需要随时检查fast指针的有效性，如果fast==NULL,直接返回空指针即可

参考代码如下：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    struct ListNode* slow = pListHead,*fast = pListHead;
    if(pListHead)
    {
        while(k--)
        {
            if(fast == NULL)
            {
                return fast;
            }
            fast = fast->next;
        }
        while(fast)
        {
            slow = slow->next;
            fast = fast->next;
        }
    }

    return slow;

}

到了这里，关于【leetcode】链表的中间节点|链表中倒数第k个节点的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！