【数据结构与算法 刷题系列】求链表的中间结点

一、问题描述

二、解题思路

1.计数器方式

实现比较简单，但效率相对较低

1. 首先创建一个遍历链表的指针和一个计数器变量
2. 第一次遍历链表，求得链表长度
3. 然后指针回到链表初始位置，计数器/2
4. 第二次遍历链表，找到对应位数的节点的地址
5. 返回找到的节点地址

通过计数器/2获得的位置

• 当链表为奇数个节点时，得到的是中间节点的位置
• 当链表有偶数个节点时，得到的是中间第二个节点的位置
• 当链表为空时，得到初始位置，即NULL

所以，无论何种情况都可以得到正确的结果

2.快慢指针方式

对逻辑和细节要求比较高，效率高

1. 创建两个快慢指针，初始都指向链表的首节点
2. 遍历链表，循环执行的条件是fast不为空
3. 慢指针每次向后一个节点，快指针移动两个节点
4. 奇数个元素的链表，fast指针最终会落在最后一个节点上，此时slow指向的节点即为中间节点
5. 偶数个元素的链表，fast指针最终会落在最后一个节点后面的NULL，此时slow指向的节点即为中间节点的第二个节点
6. 返回slow指针指向的地址

奇数个元素的链表的执行逻辑

1.初始状态，快慢指针都指向第一个节点

2.快慢指针各执行一次移动操作后

3.当fast->next为NULL时，不能继续移动，此时slow指针指向的就是中间节点

偶数个元素的链表的执行逻辑

1.初始状态，快慢指针都指向第一个节点

2.快慢指针各执行一次移动操作后

3.快慢指针再执行一次移动操作后

4.当fast为NULL时，不能继续移动，此时slow指针指向的就是中间节点

三、源代码实现        

1.计数器方式

struct ListNode* middleNode1(struct ListNode* head) //计数器方式
{
    struct ListNode* pcur = head;//遍历链表的指针
    int count = 0;
    while (pcur)//第一次遍历链表，求得链表长度
    {
        pcur = pcur->next;
        count++;
    }
    count /= 2;//长度/2求得中间节点在第几位
    pcur = head;//指针回到初始位置
    while (count)//第二次遍历链表，找到对应位数的节点的地址
    {
        pcur = pcur->next;
        count--;
    }
    return pcur;//如果链表为空，此处可以正确返回NULL
}

2.快慢指针方式

struct ListNode* middleNode2(struct ListNode* head) 
{
    struct ListNode*slow,*fast;//创建快慢指针
    slow=fast=head;//初始化
    while(fast&&fast->next)//当快指针可以移动两步时执行循环
    {
        slow=slow->next;//慢指针走一步
        fast=fast->next->next;//快指针走两步
    }
    return slow;//遍历完成时，slow所指节点就是中间节点
}

注意

while(fast&&fast->next)中的fast 与fast->next语句不可以调换顺序

  当链表有偶数个节点时，fast最后一次会走到NULL，fast->next对空指针解引用会报错

而当先判断fast已经为空时，因为逻辑运算符的短路问题，后面的fast->next语句不会再执行

关于短路问题更多细节可以参考C语言逻辑运算符的短路问题