java-删除链表中的重复的节点

题目描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
示例1
输入
{1,2,3,3,4,4,5}
返回值
{1,2,5}

解题思路

使用三个指针pre，tmp，cur
使用ans记录pre的初始位置，即链头节点的前一个节点（便于返回结果）
之后pre代表已经成功遍历的节点，tmp从phead开始，可能会需要删除，cur从下一个节点开始遍历
1.如果cur和tmp不等，且之前也没有出现过和tmp相等的元素，则留下tmp，tmp和cur右移。否则舍弃tmp，tmp和cur仍然右移
2.如果cur和tmp相等，则右移cur，直至出现不相等
3.注意最后cur为空时，需要判断当前tmp是否可要

Java代码

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        if(pHead==null) return pHead;
        ListNode pre=new ListNode(0);//构造一个节点，使其的尾结点指向pHead。也算作前驱节点。它的值不参与比较。多少都可以
        pre.next=pHead;
        ListNode ans=pre;//ans记录这个构造节点。从它的下一个开始就是我们要的节点
        ListNode tmp=pHead;//临时节点（当前节点的前一个）
        ListNode cur=pHead.next;//当前节点
        boolean flag=false;//记录是否出现重复
        while(cur != null){
            if(cur.val == tmp.val){//出现重复，则直接后移，并置标志位为true
                cur=cur.next;
                flag=true;
            }
            else{
                if(flag==true){//之前重复过，需要舍弃tmp节点，并三个指针整体右移
                    pre.next=cur;
                    tmp=cur;
                    cur=cur.next;
                    flag=false;
                }
                else{//直接将三个指针右移
                    pre=tmp;
                    tmp=cur;
                    cur=cur.next;
                }
            }
        }
        if(flag==true) pre.next=null;//如果重复过，但是cur==null，则舍弃tmp
        return ans.next;
    }
}