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

1. 链表和顺序表有什么区别？
2. 给定一个链表如何判断是循环链表？

因为面的是测试岗，所以要求不高。
对于问题1，参考 stackoverflow 的回答：

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

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 
 */
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 
 */
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 
         * false 
         * false 
         * true 
         * 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 = data;
        this.next = next;
    }
}

参考资料，排名代表推荐程度