LinkedList 总结

链表的题基本可以说是基础题，不涉及算法，要熟记他的一些基本操作，基本技巧。

链表的特点就是添加删除O(1)，不费空间，比如重新组合一串数字，用array需要从新开一个数组，而链表不需要，只要改变指针就行。

缺点是访问的时候，最坏可能到O(n)。

我个人一般怕乱，所以不用双向表，就用单项表挺好的。

1，dummy大法，在什么情况的时候会引入dummy点呢？一般结构是 dummy.next ＝ head， 所以dummy的作用就是一个伪头节点，在不知道head节点是否会变化的时候需要用dummy标记，以后返回的时候返回dummy.next。一般来说遇到需要head节点会变的时候就需要引入dummy点。

2，快慢指针。快慢指针可以用于：

　　1）从后向前的链表删除。－－快指针先走n步，然后快，慢指针再一起走，当快指针走到头的时候，就找到要删除的位置了。

　　2）看链表是否有环。－－快指针走2步，慢指针走1步，当快慢指针重叠的时候代表有环。此时将慢指针拉回起点，两个指针一起走，再相遇就知道环的长度。

　　3）找中点。 －－ 快走2步，慢走1步，快指针走到头，慢指针正好在1/2处。

基本操作：增（插入），删，查，翻转。

先定义链表（单向）：

public class ListNode{

　　int  val;

　　ListNode  next;

　　ListNode(int val){

　　　　this.val = val;

　　　　this.next = null;

　　}

}

     -->A-->B--> 

1，增加（插入）: 在AB中插入节点C

　　A.next = C;

　　C.next = B;

2，删除: 删除B节点

　　A.next =A.next.next;

3，查找：value＝2的

　　while (find != null && find.val != 2){

　　　　find = find.next;

　　}

4， 翻转：

　　while (head != null){

　　　　ListNode temp = head.next;

　　　　head.next = prev;

　　　　prev = head;

　　　　head = temp;

　　}　

　　prev-->A-->B-->C prev先在A点之前（prev），然后防止以后找不到A.next（也就是B）要先拿个pointer记录下这个位置。然后操作A.next（也就是head.next）指向之前的点prev。

　　prev<--A   (temp)-> B --> C  这时候A，B时断开的，肯定要再把B连到A上，那么这时候把prev移到A点，head移动到B上，准备下一次翻转。

常见错误：

1，构建一个链表时候，要有头节点（为了找到链表），还有有个tail节点，尾节点－>null，tail.next ＝ null

LinkedList 总结

原文：http://www.cnblogs.com/tritritri/p/4957828.html