文件名称：常考的数据结构题_面试常用
文件大小：29KB
文件格式：DOC
更新时间：2012-03-24 10:46:14
常考的数据结构题
常考的数据结构题 1.判断链表是否存在环型链表问题：判断一个链表是否存在环，例如下面这个链表就存在一个环： 例如N1->N2->N3->N4->N5->N2就是一个有环的链表，环的开始结点是N5这里有一个比较简单的解法。设置两个指针p1，p2。每次循环p1向前走一步，p2向前走两步。直到p2碰到NULL指针或者两个指针相等结束循环。如果两个指针相等则说明存在环。 struct link { int data; link* next; }; bool IsLoop(link* head) { link* p1=head, *p2 = head; if (head ==NULL || head->next ==NULL) { return false; } do{ p1= p1->next; p2 = p2->next->next; } while(p2 && p2->next && p1!=p2); if(p1 == p2) return true; else return false; } 2,链表反转 单向链表的反转是一个经常被问到的一个面试题，也是一个非常基础的问题。比如一个链表是这样的： 1->2->3->4->5 通过反转后成为5->4->3->2->1。最容易想到的方法遍历一遍链表，利用一个辅助指针，存储遍历过程中当前指针指向的下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往后面继续遍历。源代码如下：