某互联网公司面试题(二)

接上贴http://lgsun592.iteye.com/admin/blogs/1066179 ，这也是其中的一道面试题

问题：一个链表可能包含环，如何检测并确定环的位置，如图：



 


方法有2：

1.记录法，通过某种方式把访问过的记录记录下来，然后访问下一个节点的时候查询下访问记录（我当时只想到了此方法，唉）；

如果是外部标记的话，需要遍历1+2+...+(P+L-1)+P+(P+L)个节点，约O((max(P,L))^2)，程序实现的就是此种方法

如果是内部标记的话，只需要遍历P+L个节点，速度最快的了

推理：
KL = P + C
=>
KL - C = P

 

第二次相遇后，可以获得P的值，那么就可以确定此环形的起止位置了（程序实现的是K=1的情况）

废话不多说了，看代码吧

/**  
 * Class @CircleLinklist.java
 * 环形链表检测
 * @author  lgsun
 * Date: 2011-6-2
 */

package org.lgsun.linklist;

import java.text.MessageFormat;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

@SuppressWarnings("all")
public class CircleLinklist<E>
{
	private static final int LENGTH = 16;
	private Entry<E> header;

	public static void main(String[] args)
	{
		CircleLinklist<String> circle = new CircleLinklist<String>();
		circle.createLinkList();
		circle.print();
		circle.method1();
		circle.method2();
	}

	/**
	 * 方法1
	 * 1.遍历链表 
	 * 2.将访问过的节点的hashcode值保存起来 
	 * 3.如果某节点的hashcode值已经存在，那么存在环
	 */
	public void method1()
	{
		int start = -1;
		int curNum = 0;
		Entry<E> curEntry = header;
		List<Integer> codeList = new LinkedList<Integer>();

		//遍历链表 
		while (curEntry.next != null)
		{
			if (codeList.size() == 0)
			{
				codeList.add(curEntry.hashCode());
			}
			else
			{
				//如果存在，则包含环
				if (codeList.contains(curEntry.hashCode()))
				{
					start = codeList.indexOf(curEntry.hashCode());
					break;
				}
			}

			codeList.add(curEntry.hashCode());
			curEntry = curEntry.next;
			curNum++;
		}

		if (start != -1)
		{
			System.out.println(MessageFormat.format(
					"方法1：此链表中包含环，从第{0}个节点到第{1}个节点。", start, curNum));
		}
		else
		{
			System.out.println("方法1：此链表中不包含环!");
		}
	}

	/**
	 * 方法2
	 * 追赶法，数学啊，数学
	 */
	public void method2()
	{
		int start = 0;
		int length = 0;
		boolean isCircle = false;
		Entry<E> firstEntry = header;
		Entry<E> secondEntry = header;

		//第一次，p1 速度为1，p2速度为2
		while (secondEntry != null)
		{
			length++;
			if (length > 1)
			{
				// 直接比较内存地址
				if (firstEntry == secondEntry)
				{
					isCircle = true;
					break;
				}
			}

			if (firstEntry.next != null)
			{
				firstEntry = firstEntry.next;
			}
			else
			{
				break;
			}

			if (secondEntry.next != null)
			{
				secondEntry = secondEntry.next.next;
			}
			else
			{
				break;
			}
		}

		if (isCircle)
		{
			secondEntry = header;

			//第二次，p1速度为1，p2速度为1
			for (int i = 0; i < length; i++)
			{
				start++;
				// 直接比较内存地址
				if (firstEntry == secondEntry)
				{
					// 从头到尾，交点总共算了3次，所以减2
					length = length + start - 2;
					break;
				}

				if (firstEntry.next != null)
				{
					firstEntry = firstEntry.next;
				}
				else
				{
					break;
				}

				if (secondEntry.next != null)
				{
					secondEntry = secondEntry.next;
				}
				else
				{
					break;
				}
			}
		}
		else
		{
			System.out.println("方法2：此链表中不包含环!");
		}

		System.out.println(MessageFormat.format(
				"方法2：此链表中包含环，从第{0}个节点到第{1}个节点。", start, length));
	}

	/**
	 * 向链表中增加节点
	 */
	public void add(Entry<E> entry)
	{
		if (header == null)
		{
			header = entry;
		}
		else
		{
			entry.next = header;
			header = entry;
		}
	}

	/**
	 * 创建一个带环的链表
	 */
	public void createLinkList()
	{
		String disturb = "disturb";

		Entry footer = null;
		Entry node = new Entry<String>("node");

		Random random = new Random();

		for (int i = 0; i < LENGTH; i++)
		{
			// 在长度1/2处加入指定节点
			if (i == (LENGTH / 2))
			{
				add(node);
			}
			else if (i == (LENGTH / 4) || i == (LENGTH * 3 / 4))
			{
				// 加入干扰节点
				add(new Entry(disturb));
			}
			else
			{
				// 加入随机节点
				String e = String.valueOf(random.nextInt(9999));
				add(new Entry(e));
			}

			// 获取尾节点
			if (i == 0)
			{
				footer = header;
			}
		}

		// 给尾节点赋值为确定节点，产生环
		footer.next = node;
	}

	/**
	 * 输出此链表
	 */
	public void print()
	{
		Entry<E> flag = header;

		System.out.print("header:");
		for (int i = 1; i < LENGTH + 4; i++)
		{
			if (i != 0)
			{
				System.out.print("=>");
			}
			System.out.print("["+i+"]"+flag.element.toString());
			flag = flag.next;
		}
		System.out.println();
		flag = header;
	}
}

class Entry<E>
{
	E element;
	Entry<E> next;

	Entry(E element)
	{
		this.element = element;
		this.next = null;
	}
}

 

       不知道发此帖是对是错，发完上一帖已经有朋友M我说，他面试的时候也碰到的同样的题了，可见此公司的题库更新很慢吗 ，希望大家早日找到自己喜欢的工作哦。

       我是在洗澡的时候完成的此题的编码构思，所以一不小心和地板来了个亲密接触


参考资料：http://blogold.chinaunix.net/u1/41845/showart_2019391.html

 

应该使用HashSet：遍历链表，在访问一个节点后，把这个节点放入HashSet中；在访问一个节点前先调用HashSet
的contains(Object node)方法来判断该节点是否已访问过，如果是，这个节点就是环的位置。


你的method1()使用了LinkedList的contains(Object node)方法。该方法会从头开始依次遍历链表来查找是否包含指定的节点，效率比较低。HashSet底层是通过包装了一个HashMap来实现的，它的contains(node)方法其实是调用HashMap的containsKey(Object node)来实现的，由于散列的缘故，这个查找的执行效率会很高。

在校学生...表示压力巨大

遍历一次链表，没次遍历一个节点，对该节点取hash，然后保存在一个hashmap中，key为hash值，value为该节点的位置，可以用一个自增i变量表示，每次访问一个节点的时候，查询下hashmap中是否已存在该节点，存在，则说明出现了一个环

这样的题没啥意义。
除非你喜欢信息奥林匹克竞赛题。

  有些东西做不出来就进不去，那就搞不定了。。。。。

这是什么问题？，他们想要什么样的人？

HULU

想进入好的公司真的需要做足功课。不过对于这些算法题，我不行，也不打算浪费青春去学。

我觉着还是别去吧，这样的所谓的算法题没市场的。