【数据结构】给出一个链表，遍历一次就找到中间节点

</pre><pre name="code" class="plain"><span style="font-family: Arial,Helvetica,sans-serif;"><pre name="code" class="cpp">// 13_1_7.cpp : Defines the entry point for the console application.</span>

//

#include "stdafx.h"
#include <stdio.h>  
#include <conio.h>  
#include <string.h>  
#include <iostream>  
using namespace std;

typedef struct student
{
	int data;
	struct student *next;
}node;

node *create()
{
	node *p1,*p2,*head;
	int cycle = 1,x;
	head = (node*)malloc(sizeof(node));
	p1 = head;
	while (cycle)
	{		
		cout << "please input an integer: ";
		cin >> x;
		if (x != 0)
		{
			p2 = (node*)malloc(sizeof(node));
			p2->data = x;
			p1->next = p2;
			p1 = p2;
		}

		else
		{
			cycle = 0;
		}
	}
	head = head->next;
	p1->next = NULL;
	return head;
}

void findmid(node* head)
{
	node *p1,*mid;
	p1 = head;
	p2 = head;

	while (p1->next->next != NULL)
	{	
		p1 = p1->next->next;
		p2 = p2->next;
		mid = p2;
	}	
}

void print(node *head)
{
	node *p;
	if (head != NULL)
	{
		p = head;
		while (p != NULL)
		{
			cout << p->data << endl;
			p = p->next;
		}
	}
}

int _tmain()
{
	node *link_list = create();
	printf("The original link list is:n");
	print(link_list);
	findmid(link_list);
	return 0;
}

设置两个指针，一个每次移动两个位置，一个每次移动一个位置，当第一个指针到达尾节点时，第二个指针就达到了中间节点的位置

处理链表问题时，”快行指针“是一种很常见的技巧，快行指针指的是同时用两个指针来迭代访问链表，只不过其中一个比另一个超前一些。快指针往往先行几步，或与慢指针相差固定的步数。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!