算法面试题：快速找到未知长度单链表的中间节点

你的名字 2022-06-02 06:16 162阅读 0赞

有道算法面试题：快速找到未知长度单链表的中间节点。

你可以普通方法也可用比较好的方法，去解决这个问题。

由于单链表不知道长度，必须遍历完整个单链表才知道单恋表的长度，然后根据一般的长度去找中间结点，这是普通方法。

当然题目问的是快速找到，当然要用快速的方法啦。

这里我们**快慢指针的方法**来解决这个问题**，快指针每次走2个结点，慢指针每次走1个结点，当快指针走完链表，慢指针刚好走到中间，这就是快慢指针的核心思想**。

下面直接看代码，只要我们知道核心思想，然后把代码完善好，就ok了。代码里面也有注释，使用c写的哈。

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <string.h>
    #include <math.h>
    #include <stdlib.h>
    /*
    写一个完整的程序，实现随机生成20个元素的链表（尾插法或头插法）
    用快慢指针快速查找中间结点的值并显示。
    */
    #define OK 1;
    #define ERROR 0;
    typedef int EleType;
    typedef int Status;
    //单链表结点结构
    typedef struct LinkNode
    {
    	int data;//结点数据 此时用int
    	struct LinkNode *next;//下个结点的指针
    } LinkNode,*LinkList;
    /*
    采用尾插法创建单链表
    */
    Status CreateLinkList(LinkList* list,int num)
    {
    	//空指针 和 个数非法
    	if (!list || num < 1)
    	{
    		return ERROR;
    	}
    
    	LinkNode* node = (LinkNode*)malloc(sizeof(LinkNode));//创建头结点
    	*list = node;//链表指向头结点
    	node->next = NULL;//初始化空链表
    	//设置随机种子
    	srand((size_t)time(NULL));
    	for (size_t i = 0; i < num; i++)
    	{
    		//创建结点且赋值初始化
    		LinkNode* temp = (LinkNode*)malloc(sizeof(LinkNode));
    		temp->next = NULL;
    		temp->data = rand() % 100;
    		//新生成的结点放在单链表尾部
    		node->next = temp;
    		node = temp;
    	}
    	return OK;
    }
    /*
    通过指针返回单链表中间结点的值
    */
    Status GetMidVal(LinkList list,EleType* data)
    {
    
    	//快慢指针开始都指向 链表第一个结点
    	LinkNode* fast = list->next;
    	LinkNode* slow = list->next;
    
    	while (fast->next !=NULL)
    	{
    		//在不越界的情况下快指针每次走2个结点
    		if (fast->next->next!=NULL)
    		{
    			fast = fast->next->next;
    			slow = slow->next;//慢指针一次走1个结点
    		}
    		//当结点为偶数个时，在倒数第二个结点无法走2个结点，就走一个结点
    		else
    		{
    			fast = fast->next;
    			//fslow = slow->next;//如果想 当结点个数为偶数个时，慢指针指向 中间2个结点靠后那个结点，那么当快指针走1步时，慢指针也走1步。
    		}
    	}
    	/*
    	当前快指针走完链表时，慢指针刚好走到 中间结点。
    	实际上当结点数是奇数时 慢指针 走到 中间结点，
    		  当结点数是偶数时，此时中间结点有2个，此时慢指针指向靠前那个结点。
    	举个例子 1 3 5 7 9 快指针第一次走到 5 第二次走到 9 然后链表走完，慢指针走2步 刚好走到 中间结点5
    			 1 3 5 7   快指针第一次走到 5 第二次越界只走一步然后链表走完，快指针走2步慢指针走1步，快指针走1步时慢指针没有走，故慢指针 走到结点 3。
    			 如果想 当结点个数为偶数个时，慢指针指向 中间2个结点靠后那个结点，那么当快指针走1步时，慢指针也走1步。
    	*/
    	*data = slow->data;
    
    	return OK;
    }
    /*
    展示单链表数据
    */
    void ShowLinkList(LinkList list)
    {
    	LinkNode* node = list->next;//node开始指向第一个结点
    	while (node)
    	{
    		printf("%d ", node->data);
    		node = node->next;
    	}
    	printf("\n");
    }
    int main(int argc, char *argv[])
    {
    	LinkList list;
    	int mid;
    	CreateLinkList(&list,6);
    	GetMidVal(list, &mid);
    	ShowLinkList(list);
    	printf("mid = %d\n", mid);
    	return 0;
    }

验证结果：

![Center][]

![Center 1][]

做算法题大家要多积累，这样才会有算法的思维，才能做到见多识广！

[Center]: /images/20220602/b081cb1b15a74022bff95834eb098885.png
[Center 1]: /images/20220602/dd11eb71063c400ba3410c9c6ffd7790.png