删除链表中重复的节点

《剑指offer》刷题笔记。如有更好解法，欢迎留言。

关键字：链表

题目描述：

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

思路：

1. 因为需要删除重复的节点，而且该链表是单向链表，一般我们考虑使用两个指针（pre和cur），为此添加虚拟节点Head

2. 创建指针pre和cur

3. 通过while循环判断 cur 和 cur.next 的值是否相等，当没碰到重复时 pre 和 cur 一直往后移动。


4. 遇到 cur 和 cur.next 的值相等的情况时停止移动。通过while循环再判断到底有多少个重复节点，cur 单独移动。

5. 到这一步，开始删除 3 这个节点。



6. 到这里节点 3 已经被删除了，同理删除剩余的节点 4。最后返回Head.next（也就是原来的头结点）。

• 完整代码

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function deleteDuplication(pHead)
{
    if(pHead === null || pHead.next === null){
        return pHead;
    }
    let Head = new ListNode(0);
    Head.next = pHead;
    let pre = Head;
    let cur = Head.next;
    while(cur !== null){
        if(cur.next !== null && cur.val === cur.next.val){
            while(cur.next !== null && cur.val === cur.next.val){
                cur = cur.next;
            }
            pre.next = cur.next;
            cur = cur.next;
        }else{
            pre = pre.next;
            cur = cur.next;
        }
    }
    return Head.next;
}