返回链表的中间结点
给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。
用快慢指针来写:
Node* Fast;
Node* Slow;
先初始化,让Fast和Slow都指向第一个链表节点,然后让Fast每次移动两位,Slow每次移动一位,这样,Fast的路程就是Slow的两倍,当Fast到链表的末尾的时候,Slow也就到了链表的中间位置了。我们只需要返回Slow就可以了。
结束的条件就是当Fast为NULL或者Fast->next为NULL。
核心代码如下:
//初始化
Node* Fast=head;
Node* Slow=head;
//快慢指针操作
while(Fast&&Fast->next){
Fast=Fast->next->next;
Slow=Slow->next;
}
当然还要考虑链表的个数,可能为奇数,也可能为偶数。
当链表为奇数时:
当链表为偶数时: