寻找链表中间节点-一种高效的算法

链表（特别是单链表）的定位是链表这种数据结构的一个软肋所在，定位某一个元素你

就不得不通过遍历的方式获得。如果要寻找一个单链表的中间节点，普通的方法就是先遍历得到链表的长度，然后再通过长度遍历得到链表的中间节点。当然有一些链表通过一个特殊的头节点记录链表的长度的情况，可能要简单一些。

?????? 前一段时间，在看链表的归并排序的时候，就不得不面临着寻找链表中间节点的问题。这里给出一种实现，很可能是大家想不到的：）：

1） 使用两个指针进行遍历，快指针每次步进2，慢指针每次步进1；

2） 当快指针到达链表尾部的时候，慢指针指向的就是链表的中点。

这个算法的思想和经典问题“判定链表中是否存在环”的思想是一致的，但是如果不是

有启发，真的是很难想出来：）。

实现源码为：

//main.cpp

#include <ctime>
#include <iostream>
using namespace std;

struct node
{
?????? node* _next;
?????? int _data;
?????? node(int data):_next(NULL),_data(data)
?????? {

?????? }

};


node* InitData(int NUM)
{
?????? node* head = new node(-1);
?????? node* tmp = head;

?????? for (int i = 0; i < NUM; ++i)
?????? {
????????????? head = head->_next = new node(i);
?????? }

?????? return tmp;
}


void Print(const node* head)
{

?????? while (head != NULL)
?????? {
????????????? cout<<head->_data<<" ";
????????????? head = head->_next;
?????? }
?????? cout<<endl;

}



node* find_mid_element(node* head)
{

?????? if (NULL == head) return NULL;
?????? if (head->_next == NULL) return head;
?????? if (head->_next->_next == NULL) return head;
?????? node* mid= head;

?????? node* p = mid->_next;
?????? while ((NULL != p) && (NULL != p->_next))
?????? {

????????????? mid = mid->_next;
????????????? p = p->_next->_next;
?????? }

?????? return mid;
}



int main(int argc,char* argv[])
{

?????? node* h = InitData(1000);
?????? Print(h);

?????? node* m = find_mid_element(h);?????

?????? if (m != NULL)
????????????? cout<<m->_data<<endl;
?????? return 0;

}

（编辑：北几岛）

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

?2008-09-19 20:55