题目：
给出一个排好序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
例如：
给出的链表为1->2->3->3->4->4->5, 返回1->2->5.
给出的链表为1->1->1->2->3, 返回2->3.
思路：
1.思路在于当前的值跟下一个值比较，如果重复，删除下一个，如果不重复，就继续遍历下一个元素
2.要把所有的重复值节点都删完，考虑当前的值即使跟下一个不相等，也有可能与之前重复过的相等
3.使用一个计数器，如果有与当前节点重复的节点，删除掉重复节点之后（因为该链表是有序的，所以重复的就是当前节点的下一个），计数器的值加一。当前节点重复值删除完之后，判断当前节点是否需要删除就是判断计数器的值是否为0，如果不是0则删除该节点。然后继续遍历
4.两种特殊情况，当前节点有重复在链表的头和链表的尾。当为头的时候，因为该链表是不带表头的节点，所以有两种解法，加虚拟表头结点或者分为判断是否为为表头结点，是和不是分为两种情况。对于尾节点来说，因为出循环之后还要判断尾节点是否重复过，如果重复过，删除尾节点。
代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
//添加一个虚拟的表头结点
ListNode tempHead = new ListNode(0);
tempHead.next = head;
//pre之前虚拟头结点，记录元素的前一个位置，如果要删除当前元素，需要前一个位置的指针
ListNode cur = head, pre = tempHead;
//计数器的初始值置为0
int count = 0;
//当前链表为空或者遍历到链表的最后一个元素时
while (cur != null && cur.next != null) {
//如果当前节点和下一个结点相等，删除下一个结点，计数值加1
if (cur.val == cur.next.val) {
cur.next = cur.next.next;
count++;
} else {
//不相等的情况下需要判断计数值是否为0来确定是否需要删除当前节点
if (count > 0) {
pre.next = cur.next;
count = 0;
} else {
pre = cur;
}
cur = cur.next;
}
}
//判断尾节点是否需要删除
if (count > 0) {
pre.next = cur.next;
}
//返回去除虚拟头结点的链表
return tempHead.next;
}
}
网友评论