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

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

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



 


方法有2：

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

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

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

2.追赶法，类似在操场跑圈，两人同时起步，快的人和慢的人第一次相遇的时候，快的肯定比慢的多跑一圈，以此进行推算

第一次跑：两人同时从起点出发，第一个人P1速度为1，第二个人P2速度为2，相遇的时候P1跑的路程N=P+C，P2的路程=2N，可以推出此园的周长KL=P+C=N(K=1,2...)

第二次跑：P1的接上次位置，速度为1，P2从起点出发，速度为1，这次经过距离P后2人相遇，即在圆的起点相遇

推理：
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

 

评论

17 楼 sebatinsky 2011-06-08  

菜鸟从中飞过，，，。心慌慌。

16 楼 marshaldong 2011-06-08  

两层循环，如果内层循环的节点有等于外层循环的节点的，说明有环，后续分享代码：

public class TestCircularList {
	static class Node<T> {
		T value;
		Node<T> next;

		Node(Node<T> next, T value) {
			this.value = value;
			this.next = next;
		}

	}

	public static Node<Integer> generateLinkList(int number) {
		Node<Integer> t = new Node<Integer>(null, 0);
		Node<Integer> temp = t;
		Node<Integer> temp1 = null;
		for (int i = 1; i < number; i++) {
			temp1 = new Node<Integer>(null, i % number);
			temp.next = temp1;
			temp = temp1;
		}
		temp.next = t.next.next.next;// construct circular linked list
		return t;
	}

	public static void main(String[] args) {
		Node<Integer> node = TestCircularList.generateLinkList(10);
		TestCircularList.traverse(node, 10);
	}

	/**
	 * 
	 * @param <T>
	 * @param node
	 *            the head node
	 * @param length
	 *            the actural number of nodes of the linked list
	 */
	public static <T> void traverse(Node<T> node, int length) {
		Node<T> temp = node;
		Node<T> temp1 = null;
		while (temp != null) {
			temp1 = temp.next;
			int tailIndex = --length;
			while (temp1 != null && tailIndex != 0) {
				if (temp1 == temp) {
					System.out.println("has rings!");
					System.out.println("Begin node value: " + temp.value);
					while (temp.next != temp1) {
						System.out.println(temp.next.value);
						temp = temp.next;
					}
					System.out.println("End node value: " + temp.value);
					return;
				}
				temp1 = temp1.next;
				tailIndex--;
			}
			temp = temp.next;
		}
	}
}

似乎和找出一个List里两个值相同的元素的索引是一个解法，只不过这里是比较两个节点的相等（内存地址相同），再思考。

15 楼 enefry 2011-06-07  

支持hashMap说法.遍历是必须的.只是需要多余空间的支持.

14 楼 fivestarwy 2011-06-07  

Durian 写道

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

普通的数据结构习题，信息奥林匹克不知道比这难多少倍

13 楼 antonia 2011-06-07  

这些题目看着好难。。。。

12 楼 lance4t 2011-06-07  

别去百度浪费大好青春。。。

11 楼 java_web 2011-06-07  

唉
完全看不懂啊
学习学习啊

10 楼 wuzaizhong283 2011-06-07  

这是百度的题

9 楼 dwbin 2011-06-07  

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

8 楼 Durian 2011-06-06  

cttnbcj 写道

Durian 写道

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

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

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

7 楼 thihy 2011-06-06  

avi2 写道

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

HULU

6 楼 avi2 2011-06-06  

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

5 楼 cttnbcj 2011-06-06  

Durian 写道

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

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

4 楼 Durian 2011-06-06  

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

3 楼 wyp12 2011-06-06  

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

2 楼 小怪兽 2011-06-06  

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

1 楼 asst2003 2011-06-05  

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


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