某司软件测试工程师面试题：链表相关在两家公司面试时被均被考核到链表

　　dsa_linkedlist

　　在两家公司面试时被均被考核到链表，具体问题如下：

　　1、链表和顺序表有什么区别？

　　2、给定一个链表如何判断是循环链表？

　　因为面的是测试岗，所以要求不高。

　　对于问题1，参考 stackoverflow 的回答：

　　stackoverflow:When to use LinkedList over ArrayList?

　　针对其中的部分描述，编写了测试代码进行验证：

　　package testing.interview;

　　import java.util.ArrayList;

　　import java.util.Date;

　　import java.util.LinkedList;

　　/**

　　* Print the time of linkedList and arrayList by add element 100000 times.

　　* @author lishoujun http://github.com/lishoujun/java-learn

　　public class LinkedListAdd {

　　public static void main(String[] args) {

　　final int size = 100000;

　　LinkedList<Integer> linkedList = new LinkedList<>();

　　long linkedListAddStartTime = new Date().getTime();

　　System.out.println(linkedListAddStartTime);

　　for (int i = 0; i < size; i++) {

　　linkedList.add(0, i);

　　}

　　long linkedListAddEndTime = new Date().getTime();

　　System.out.println("linkedListTime:" + (linkedListAddEndTime - linkedListAddStartTime));

　　ArrayList<Integer> arrayList = new ArrayList<>();

　　long arrayListStartTime = new Date().getTime();

　　for (int i = 0; i < size; i++) {

　　arrayList.add(0, i);

　　}

　　long arrayListEndTime = new Date().getTime();

　　System.out.println("arrayListTime:" + (arrayListEndTime - arrayListStartTime));

　　// for debug

　　try {

　　Thread.sleep(100000);

　　} catch (InterruptedException e) {

　　e.printStackTrace();

　　}

　　对于问题2

　　package testing.interview;

　　/**

　　* A hasCycle function to check is there a Cycle in LinkedList.

　　* the LinkedList is a simple edition just has an int data and a Node as next.

　　* @author lishoujun http://github.com/lishoujun/java-learn

　　public class LinkedListCycle {

　　public static void main(String[] args) {

　　System.out.println(hasCycle(null));

　　System.out.println(hasCycle(new Node(1, null)));

　　System.out.println(hasCycle(new Node(1, new Node(1, null))));

　　Node first = new Node(1, null);

　　first.next = first;

　　System.out.println(hasCycle(first));

　　Node second = new Node(1, first);

　　first.next = second;

　　System.out.println(hasCycle(first));

　　/**

　　* result:

　　* false

　　* true

　　}

　　public static boolean hasCycle(Node start) {

　　if (start == null || start.next == null)

　　return false;

　　Node tmp = start;

　　Node current = start.next;

　　while (current.next != null) {

　　if (tmp == current) {

　　return true;

　　}

　　current = current.next;

　　}

　　return false;

　　}

　　class Node {

　　int data;

　　Node next;

　　Node() {

　　}

　　Node(int data, Node next) {

　　this.data = http://www.gunmi.cn/v/data;

　　this.next = next;

　　}