在处理链表的删除操作时，一般先找到待删除结点的前驱，否则会断链。而对于没有虚拟头结点的链表，删除第一个结点不好处理，因为没有头结点（但不影响删除最后一个结点），此时就需要构造一个虚拟头结点，可以更方便的完成所有可能的删除操作。
题目1：删除链表中所有值为val的结点，如1->2->6->3->4->5->6->null，要求删除值为6的结点，返回1->2->3->4->5->null。
公用代码：
public class ListNode { public int val; public ListNode next; public ListNode(int x) { this.val = x; this.next = null; } public static ListNode createList(int[] nums) { if(null == nums || 0 == nums.length) return null; ListNode head = new ListNode(nums[0]); ListNode needle = head; for(int i = 1; i < nums.length;++i) { ListNode node = new ListNode(nums[i]); needle.next = node; needle = needle.next; needle.next = null; } return head; } }我们先给出不用虚拟头结点完成链表删除操作的过程，看看具体繁琐在哪？
// 203 没有虚拟头结点的情况下需要下面的判断才能处理val等于头结点的情况 public ListNode removeElements(ListNode head, int val) { // 循环处理头结点（有多个与头结点值相同的结点，且删除的就是它们） while (head != null && head.val == val) { // head一直在变换 head = head.next; } // 在进行下面的while循环之前判断一下 if (head == null) return null; // 下面的逻辑是删除非头结点（删除头结点在上面已经处理了） ListNode pre = head; while (pre.next != null) { // 找到了要删除的结点 if (pre.next.val == val) pre.next = pre.next.next; else // 没有找到直接移动指针遍历下一个结点即可 pre = pre.next; } return head; }上面的处理需要单独处理头结点，下面这段程序是通过添加了一个虚拟头结点来避免这种情况。
// 203 添加了虚拟头结点，更简单且便于理解 public ListNode removeElements1(ListNode head, int val) { // 创建一个虚拟头结点，这样不用单独处理头结点 ListNode dummyHead = new ListNode(-1); dummyHead.next = head; ListNode pre = dummyHead; // 从实际的头结点开始遍历，但是保证了实际的头结点具有自己的前驱 while (pre.next != null) { // 找到了要删除的结点 if (pre.next.val == val) pre.next = pre.next.next; else// 没找到了要删除的结点，直接遍历下一个结点 pre = pre.next; } // 一定注意dummyHead指向一只未变化，变化的是临时指针pre return dummyHead.next; }题目2：给定一个有序链表，将其中有重复的元素全部删除
如1->2->3->3->4->4->5->null，返回1->2->5；再如1->1->1->2->3，返回2->3。
实现方式一：使用检查表的方式，效率较低。
import java.util.ArrayList; import java.util.List; public class Solution { public ListNode deleteDuplicates(ListNode head) { if (null == head) return null; ListNode pointer = head; List<Integer> tmpList = new ArrayList<Integer>(); int index = -1; // 记录想等元素的个数，避免漏删 int equalCnt = 1; while (pointer != null) { int value = pointer.val; // 临时列表中不存在，就添加进去，对应的索引值加1，只是添加重复元素的第一个值 if (!tmpList.contains(value)) { // 尝试删除所有值等于上一个元素值的元素，有则删除 if (equalCnt > 1) { tmpList.remove(index--); } // 添加新的元素 tmpList.add(value); index++; // 将新元素的equalCnt置为1 equalCnt = 1; } else {// 临时列表中存在，不添加只记录重复元素的个数，以便下面的删除操作 equalCnt++; // 最后一个元素与前面的元素重复的情况 if (null == pointer.next) tmpList.remove(index--); } // 指针后移，遍历下一个链表元素 pointer = pointer.next; } // 使用虚拟头结点从新创建一个链表，这种方法思路简单，辅助空间大 ListNode dummyHead = new ListNode(-1); ListNode cur = dummyHead; for (Integer tmp : tmpList) { cur.next = new ListNode((int) tmp); cur = cur.next; } return dummyHead.next; } public static void main(String[] args) { int[] nums = { 1, 1 }; ListNode link = ListNode.createList(nums); ListNode result = new Solution().deleteDuplicates(link); while (null != result) { System.out.print(result.val + " "); result = result.next; } } }实现方式二：使用两个列表作为检查表，记录元素出现的次数，但是使用map不行，因为map存储数据的时候会根据hash值进行排序，导致乱序。例如{2,1}，输出为1->2。
import java.util.ArrayList; import java.util.List; class Solution { public ListNode deleteDuplicates(ListNode head) { if (null == head) return head; // 定义两个list来充当检查表，valus表示元素的值，times表示对应值出现的次数 List<Integer> values = new ArrayList<Integer>(); List<Integer> times = new ArrayList<Integer>(); int time = 1; boolean first = true; while (head != null) { int value = head.val; // 第一个结点需要特殊处理 if (!values.contains(value)) { // 将上一个元素的出现次数添加到times中 if (!first) // 第一个元素出现的次数到与他值不同的元素出现时才添加 times.add(time); // 添加新元素到values中 values.add(value); // 重置time time = 1; } else // 元素重复时出现次数加1 time++; head = head.next; first = false; // 到了最后一个结点，需要特殊处理来记录最后一个元素出现的次数 if (head == null) times.add(time); } // 定义一个虚拟结点 ListNode dummyHead = new ListNode(-1); // 定义一个穿针引线的指针，让它去串连所有合法的结点，头结点只指向头结点，不需要移动， // 且一定将该指针与头结点建立联系，否则会断链 ListNode tmpNode = dummyHead; for (int i = 0; i < times.size(); ++i) { if (1 == times.get(i)) { tmpNode.next = new ListNode(values.get(i)); tmpNode = tmpNode.next; } } return dummyHead.next; } public static void main(String[] args) { int[] nums = { 1, 1, 1, 2 }; ListNode link = ListNode.createList(nums); ListNode result = new Solution().deleteDuplicates(link); while (null != result) { System.out.print(result.val + " "); result = result.next; } } }实现方式三：使用双指针直接操作链表，效率更高。
public class LC82 { public ListNode deleteDuplicates(ListNode head) { ListNode dummyHead = new ListNode(-1); dummyHead.next = head; ListNode previous = dummyHead; // 从头结点开始遍历，因为要删除所有重复的结点，要考虑前驱previous下的两个位置的结点。 while (previous.next != null && previous.next.next != null) { if (previous.next.val == previous.next.next.val) { int dupValue = previous.next.val; while (previous.next != null && previous.next.val == dupValue) { previous.next = previous.next.next; } } else { previous = previous.next; } } return dummyHead.next; } public static void main(String[] args) { int[] nums = { 2, 1 }; ListNode link = ListNode.createList(nums); ListNode result = new LC82().deleteDuplicates(link); while (null != result) { System.out.print(result.val + " "); result = result.next; } } }
