链表 - LinkedList

基本概念

链表和数组类似，但相比于数组，链表有动态大小。而且插入和删除的效率很高，只要O(1)的时间。但是链表的遍历效率并不高。
Java中，链表为LinkedList类，每个节点由内置静态类Node实现：

private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
}

这种链表为双向链表，每个节点储存它前面的节点，后面的节点，以及它自身的值。也可以去掉节点的prev属性，变为单向链表。

基本操作

Java中LinkedList类的方法。

LinkedList<Integer> l = new LinkedList<>();
l.size(); // 链表的长度
l.get(); // 返回链表某个位置的元素
l.add(); // 向链表某个位置添加元素
l.addFirst(); // 向链表头添加元素
l.addLast(); // 向链表尾添加元素
l.remove(); // 删除链表某个位置的元素

Lintcode相关题目

• 遍历
  Convert Linked List to Array List
  Convert Array List to Linked List
  Count Linked List Nodes
• 反转
  Reverse Linked List
  Reverse Linked List II
  Reverse Nodes in K Group
• 合并
  Merge Two Sorted Lists
  Merge k Sorted Lists
• 递归
  Linked List Weighted Sum in Reverse Order
  Reverse Order Storage
• 其他
  Copy List with Random Pointer
  Linked List Cycle
  Linked List Cycle II