题目:求链表的中间结点。如果链表中结点总数为奇数,返回中间结点;如果结点总数是偶数,返回中间两个结点的任意一个。
思路:定义两个指针,一个指针一次走一步,另一个指针一次走两步,当走得快的指针到达链表末尾的时候,走得慢的指针刚好达到链表的中间节点。
代码:
# include<iostream>
using namespace std;
struct ListNode
{
int key;
ListNode *next;
ListNode():next(NULL),key(0){}
};
ListNode *FindMiddleNode(ListNode *head)
{
if(head == NULL )
{
return NULL;
}
ListNode *fast=head;
ListNode *slow=head;
while(fast->next != NULL)
{
if(fast->next->next != NULL)
{
slow=slow->next;
fast=fast->next->next;
}
else
{
slow=slow->next;
}
}
return slow;
}
int main()
{
ListNode *l1=new ListNode();
ListNode *l2=new ListNode();
ListNode *l3=new ListNode();
ListNode *l4=new ListNode();
ListNode *l5=new ListNode();
ListNode *l6=new ListNode();
ListNode *l7=new ListNode();
l1->next=l2;
l2->next=l3;
l3->next=l4;
l4->next=l5;
l5->next=l6;
l6->next=l7;
l1->key=1;
l2->key=5;
l3->key=86;
l4->key=16;
l5->key=34;
l6->key=94;
l7->key=100;
ListNode *tmp=FindMiddleNode(l1);
cout<<tmp->key<<endl;
return 0;
}