[数据结构与算法] C语言实现查找链表中间结点

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> C语言实现查找链表中间结点 -> 正文阅读

[数据结构与算法]C语言实现查找链表中间结点

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

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

#include<stdio.h>
#include<stdlib.h> 
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<stdio.h>
#include<stdlib.h> 
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;
}