C语言实现查找链表中间结点

如果链表有奇数个结点，就直接返回中间的结点，如果有偶数个结点，就有两个中间结点返回中间第二个结点
比如
[1,2,3,4,5]中间结点是3
[1,2,3,4,5,6]中间结点是4

一、通过链表长度进行计算
1. 计算链表结点个数需要遍历一次，所以首先遍历一次链表，计算链表结点个数。
2. 计算出结点个数，然后计算中间结点，无论是奇数还是偶数都是length/2+1。
3. 找出这个结点返回即可。

#include
#include 
struct ListNode* middleNode(struct ListNode* head);
struct ListNode {
	int val;
	struct ListNode *next;
};

int main(){
	// 申请结点 
	struct ListNode* lnode1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* lnode2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* lnode3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* lnode4 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* lnode5 = (struct ListNode*)malloc(sizeof(struct ListNode));
	lnode1->val=1;
	lnode2->val=2;
	lnode3->val=3;
	lnode4->val=4;
	lnode5->val=5;
	lnode1->next=lnode2;
	lnode2->next=lnode3;
	lnode3->next=lnode4;
	lnode4->next=lnode5;
	lnode5->next=NULL;
	ListNode* temp = middleNode(lnode1);
	while(temp!=NULL){
		printf("%d",temp->val);
		temp=temp->next;
	}
	return 0;	
}

struct ListNode* middleNode(struct ListNode* head){
	// 指向头结点 
	struct ListNode* p = head;
	int length=0;
	int middle;
	// 计算长度 
	while(p!=NULL){
		length++;
		p=p->next;
	}
	// 寻找中间结点位置 
	middle=length/2+1;
	// 再次指向头结点 
	p = head; 
	// 寻找中间结点 
	for(int i=1;i<middle;i++){
		p=p->next;
	}
	return p;
}

二、通过两个指针一个快指针，一个慢指针。
快指针走两步，慢指针走一步，最后快指针走到末尾，慢指针就是指向中间结点

#include
#include 
struct ListNode* middleNode(struct ListNode* head);
struct ListNode {
	int val;
	struct ListNode *next;
};

int main(){
	// 申请结点 
	struct ListNode* lnode1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* lnode2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* lnode3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* lnode4 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* lnode5 = (struct ListNode*)malloc(sizeof(struct ListNode));
	lnode1->val=1;
	lnode2->val=2;
	lnode3->val=3;
	lnode4->val=4;
	lnode5->val=5;
	lnode1->next=lnode2;
	lnode2->next=lnode3;
	lnode3->next=lnode4;
	lnode4->next=lnode5;
	lnode5->next=NULL;
	ListNode* temp = middleNode(lnode1);
	while(temp!=NULL){
		printf("%d",temp->val);
		temp=temp->next;
	}
	return 0;	
}
struct ListNode* middleNode(struct ListNode* head){
	// 快指针
	struct ListNode* p = head;
	// 慢指针
    struct ListNode* q = head;
	while(p!=NULL&&p->next!=NULL){
		q=q->next;
		p=p->next->next;
	} 
	return q;
}