给你单链表的头结点 head ,请你找出并返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。
Definition for singly-linked list.
struct ListNode {
int val;
struct ListNode *next;
};
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
ListNode* slow=head;
ListNode* fast=head;
while(fast && fast->next)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
这个题和快慢指针有些相似。创建临时变量slow和fast都表示头节点。
当slow走到下一个节点的时候,fast走到了下一个节点的下一个节点。也就是fast走两个slow走一个。
当链表为奇数个时,fast到最后一个节点的时候slow刚好到中间节点。当链表为偶数个时,slow走到两个中间节点第二个节点的时候,fast则应该是到了链表最后一个节点的下一个节点。所以我们while循环的判断条件是fast不为空且fast的next指针指向的位置不为空。
最后返回中间节点。