82. 删除排序链表中的重复元素 II

题意：

解题思路：

思路：双指针遍历：O(n)
1. 首先定义虚拟元素dummy指向链表头节点
2. 从前往后扫描，遇到区间段相同的元素则直接删除；
3. 调整指针指向，最后返回dummy->next

PHP代码实现：

class Solution {
    /**
     * @param ListNode $head
     * @return ListNode
     */
    function deleteDuplicates($head) {
        return $this->deleteDuplicates1($head);
        if (!$head) return null;
        $dummy = new ListNode(0);
        $dummy->next = $head;
        $p = $dummy;
        //1->2->3->3->3->4->4->5
        while ($p->next && $p->next->next) {
            if ($p->next->val == $p->next->next->val) {
                $num = $p->next->val;
                //出现3个3的情况，指针继续往后找，直到下个元素不等
                while ($p->next && $p->next->val == $num) {
                    $p->next = $p->next->next;
                }
            } else {
                $p = $p->next;
            }
        }
        return $dummy->next;
    }
    function deleteDuplicates1($head) {
        $dummy = new ListNode(0);
        $dummy->next = $head;
        $prev = $dummy;
        $cur = $prev->next;
        while ($cur != null) {
            while ($cur->next != null && $cur->val == $cur->next->val) {
                $cur = $cur->next;
            }
            if ($prev->next != $cur) {
                $prev->next = $cur->next;
            } else {
                $prev = $prev->next;
            }
            $cur = $prev->next;
        }
        return $dummy->next;
    }
}

GO代码实现：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    dummy := &ListNode {
        Val : -1,
        Next : head,
    }
    p := dummy
    for p.Next != nil && p.Next.Next != nil {
        if p.Next.Val == p.Next.Next.Val {
            num := p.Next.Val
            for p.Next != nil && p.Next.Val == num {
                p.Next = p.Next.Next
            }
        } else {
            p = p.Next
        }
    }
    return dummy.Next
}