寻找单链表的中间项

ゝ一纸荒年。 2023-01-16 06:38 112阅读 0赞

## 问题：寻找一条单链表中的中间项的值。 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1_size_16_color_FFFFFF_t_70_pic_center]

*  链表结构体

typedef struct Node{
        
    	int value;
    	struct Node* next;
    }*Link;

*  思路：使用**快慢指针**，设置两个指针（slow，fast）分别指向链表第一项，slow每次移动一次（`slow = slow.next`） ,fast 每次移动两次（`fast = fast.next.next`），当fast遍历完整条链表后，slow的位置即是中间项的位置。
 *  **动画模拟**：  
    ![在这里插入图片描述][20210424152301680.gif_pic_center]
 *  **代码实现：**

int findMid(Link head){
        
    	if(head == NULL || head->next == NULL){
        
    		return -1;
    	}
    	// 定义两个指针指向链表第一项
    	Link slow = head->next,fast = head->next;
    	// 两个指针遍历链表，当快指针指向的结点没有下一结点时，结束循环。
    	while(fast!=NULL  && fast->next!=NULL){
        
    		slow = slow->next;
    		fast = fast->next->next;
    	}
    	return slow->value;
    }

**效果：**  
奇数长度链表  
![在这里插入图片描述][20210424152213645.png_pic_center]  
偶数长度链表  
![在这里插入图片描述][20210424152144371.png_pic_center]

完整测试代码：

#include<stdio.h>
    #include<stdlib.h>
    
    typedef struct Node{
        
    	int value;
    	struct Node* next;
    }*Link;
    
    Link rearCreateLink(int n);
    void print(Link head);
    int findMid(Link head);
    int main(){
        
    	int n;
    	Link L2;
    	scanf("%d",&n);
    	L2 = rearCreateLink(n);
    	printf("%d",findMid(L2));
    	return 0;
    }
    Link rearCreateLink(int n){
        
    	Link head,rear,newNode;
    	head = (Link)malloc(sizeof(struct Node));
    	head->next = NULL;
    	rear = head;
    	while(n--){
        
    		newNode = (Link)malloc(sizeof(struct Node));
    		scanf("%d",&newNode->value);
    		newNode->next = rear->next;
    		rear->next = newNode;
    		rear = rear->next;
    	} 
    	return head;
    }
    void print(Link head){
        
    	Link link;
    	if(head == NULL || head->next == NULL){
        
    		printf("此链表为空！\n");
    		return ;
    	}
    	link = head->next;
    	while(link!=NULL){
        
    		printf(" %d ",link->value);
    		link = link->next;
    	}
    	printf("\n");
    }
    int findMid(Link head){
        
    	if(head == NULL || head->next == NULL){
        
    		return -1;
    	} 
    	Link slow = head->next,fast = head->next;
    	while(fast!=NULL  && fast->next!=NULL){
        
    		slow = slow->next;
    		fast = fast->next->next;
    	}
    	return slow->value;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/3f2690c0be46424191ecac06faae14c2.png
[20210424152301680.gif_pic_center]: /images/20221022/8044435a60fb4aaea771fd2c6ead2f8a.png
[20210424152213645.png_pic_center]: /images/20221022/df65ae068908418cb08ef60045895363.png
[20210424152144371.png_pic_center]: /images/20221022/ff1efc3dde1d428595f4e7eec4d353c2.png