在链表里如何发现循环链接？_微软笔试题

牛客787908号

1.循环链表的特点是收尾相接，没有头指针，也没有尾指针。如果去遍历循环链表，则是死循环。

2.这里判断循环链表的方法是; 用两个指针，一个是慢指针（跳一个节点遍历），一个是快遍历（p=p.next.next跳两个节点遍历)，如果2个指针不能碰到,说明单向链表不存在循环;如果2个指针能够碰到,说明单向链表存在循环.源代码如下：

package com.base.program;

public class CircularLinkedList {

class Element {

public Object value = null;

public Element next = null;

}

private Element header = null;// 头结点

/***

* 初始化链表

*/

void initList() {

header = new Element();

header.value = null;

header.next = header;

}

/***

* 插入链表

*

* @param o

*/

void insertList(Object o) {

Element e = new Element();

e.value = o;

if (header.next == header) {// 第一次插入

header.next = e;

e.next = header;

} else {// 不是第一次插入

Element temp = header;

while (temp.next != header) {

temp = temp.next;

}

temp.next = e;

e.next = header;

}

/***

* 删除链表元素

*

* @param o

*/

void deleteList(Object o) {

Element temp = header;

if (temp.next.value.equals(o)) {

temp.next = temp.next.next;

} else {

temp = temp.next;

}

/***

* 获取链表指定位置的节点

*

* @param i

* @return

*/

Element getList(int i) {

if (i <= 0 || i > size()) {

System.out.println("获取链表的位置有误，返回是null");

return null;

} else {

int count = 0;

Element e = new Element();

Element temp = header;

while (temp.next != header) {

count++;

if (count == i) {

e.value = temp.next.value;

}

temp = temp.next;

}

return e;

}

/***

* 判断链表中是否包含元素

*

* @param o

* @return

*/

boolean isContain(Object o) {

Element temp = header;

while (temp.next != header) {

if (temp.next.value.equals(o)) {

return true;

}

temp = temp.next;

}

return false;

}

// 获取链表长度

int size() {

int size = 0;

Element temp = header;

if (temp.next != header) {

size++;

temp = temp.next;

}

return size;

}

/***

* 打印链表

*/

void print() {

System.out.println("打印链表：");

Element temp = header;

while (temp.next != header) {

temp = temp.next;

System.out.print(temp.value + "\t");

}

System.out.println();

}

boolean isCycle() {

Element temp = header.next;

Element e = temp;

while ((temp != null) && (e != null) && (e.next != null)) {

temp = temp.next;

e = e.next.next;

if (temp == e) {

return true;

}

return false;

}

public static void main(String[] args) {

CircularLinkedList clist = new CircularLinkedList();

clist.initList();

clist.insertList(1);

clist.insertList(2);

clist.insertList(3);

clist.insertList(4);

clist.insertList(5);

clist.print();

System.out.println(clist.isContain(6));

System.out.println(clist.getList(1).value);

//clist.deleteList(1);

System.out.println(clist.getList(1).value);

System.out.println(clist.isCycle());

}

发表于 2015-12-04 11:02:57 回复(0)

推荐

菜鸟葫芦娃

可以构建两个指针slow和fast，slow一次向移动一个节点，fast一次移动两个节点，如果fast和solw在某个时刻指向了同一个节点，那么该链表就有循环链接。

coder 如下：

typedef struct LinkNode
{
    int data;
     LinkNode *next;
}node;
 
void findCycleNode(node *head)
{
  node *slow,*fast;
  s0 = head;
  s1=head;
  while(（slow != NULL） &&(fast != NULL)&&(fast->next!=NULL))    { 
       slow = slow->next;
       fast = fast->next->next;
       if(slow == fast)
        {
             printf("有循环链接");
        }
   }
   if((fast == NULL) || (slow  == NULL)||fast->next==NULL)
     {
         printf("没有循环链接");
      }
}

编辑于 2015-12-04 19:39:26 回复(2)