1.删除排序链表中的重复元素
题目描述：
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回已排序的链表 。
思路： 因为要删除相同元素，很容易想到定义两个指针pre，cur。cur用来遍历链表，pre用来指向cur前一个元素，如果pre的值和cur的值相等，那么删除cur指向的元素，cur指向下一个节点，如果不相等，cur指向下一个节点，pre指向cur之前指向的节点。通过这样的操作即可删除链表中重复的元素并且保留下一个。
代码：
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head==null) {
return null;
}
ListNode cur=head.next;
ListNode pre=head;
while(cur!=null) {
if(cur.val==pre.val) {
ListNode curNext=cur.next;
pre.next=curNext;
cur=curNext;
} else {
pre=cur;
cur=cur.next;
}
}
return head;
}
}
2.删除排序链表中的重复元素 II
题目描述：
给定一个已排序的链表的头 head ，删除原始链表中所有重复数字的节点，只留下不同的数字 。返回已排序的链表 。
思路： 这里删除元素与上一题不同，这一题要删除全部重复元素，而上一题删除的同时保留一个，从而导致上一题可以轻松通过双指针解决。我这里没有按照王道的解法，因为第一题的启发，我先对链表进行删除操作，每组重复元素保留一个，但是同时也将重复的数值按链表顺序保存到一个数组中。例如：链表[1,2,2,3,4,4]经过这趟操作后变成[1,2,3,4]，同时得到[2,4]这样的数组，这个数组记录下来了仍在链表中的应该删除的重复值的节点。因此按照得到的数组再进行遍历删除，如果链表中元素值等于数组中索引指向的值则删除该节点，并且数组索引加一，这是因为经过第一次删除每个重复组只保留了一个节点在链表中，所以可以这样操作。
代码：
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head==null) {
return null;
}
if(head.next==null) {
return head;
}
ListNode pre=head;
ListNode cur=head.next;
int[] arr=new int[300];
int index=0;
while(cur!=null) {
if(pre.val==cur.val) {
//数组只记录每个重复组的一个元素
if((index>=1&&arr[index-1]!=cur.val)||index==0) {
arr[index++]=cur.val;
}
ListNode curNext=cur.next;
pre.next=curNext;
cur=curNext;
} else {
pre=cur;
cur=cur.next;
}
}
int len=index;
//定义头节点，方便后续删除操作
ListNode temp=new ListNode(101);
temp.next=head;
pre=temp;
cur=temp.next;
index=0;
while(cur!=null) {
//链表中元素值等于数组中索引指向的值则删除该节点
if(index<len&&cur.val==arr[index]) {
ListNode curNext=cur.next;
pre.next=cur.next;
cur=curNext;
index++;
} else {
pre=cur;
cur=cur.next;
}
}
return temp.next;
}
}
官方题解：
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null) {
return head;
}
ListNode dummy = new ListNode(0, head);
ListNode cur = dummy;
while (cur.next != null && cur.next.next != null) {
if (cur.next.val == cur.next.next.val) {
int x = cur.next.val;
while (cur.next != null && cur.next.val == x) {
cur.next = cur.next.next;
}
} else {
cur = cur.next;
}
}
return dummy.next;
}
}
总结： 刚做这题我确实试过两个循环，但是超出时间限制因此放弃，应该是自己思路有问题。官方的这种方法思路就是先定义一个头节点方便后续操作，如何以一个外循环遍历链表，然后内循环用来删除全部的重复元素，因为无论遍历循环以及删除元素的循环都是使用cur指针完成所以不会存在超出时间限制的问题。
