题解 | #反转链表#

思路：充分利用数组的特点。

1. 注意到题中链表长度 0<=n<=100和链表节点的值满足|val|<=100的特点， 优先考虑建立一个长度为201的计数数组arr[]，初始化为0，以val值作为数组下标，arr[val]表示值为val的节点的个数，对链表进行一次遍历， 遍历到值为val的节点，则arr[val+100]++, 这里是val+100 而不是 val 是由于 val 还可为负整数，解决办法是采取统一加一个偏置值100， 那么所有的数都变为非负整数了。 设置一前一后两个指针p,q,p指向第一次出现的节点， q从p的下一个节点开始遍历，寻找下一个不同值的节点，找到后p和q之间建立链，然后 p指向q所指的节点，q指向下一个节点。遍历结束后p->next置为NULL。

2. 复杂度分析：整个过程只遍历了一遍链表，故时间复杂度为O(n), 申请了与问题规模n无关的长度的数组（申请的数组长度只跟节点值的范围有关），故空间复杂度 为O(1)*/

    struct ListNode* deleteDuplicates(struct ListNode* head) {
        int array[201]={0};
        struct ListNode *p=head,*q;
       	if(p!=NULL){
            array[p->val+100]++;
            q=p->next;
            while(q!=NULL){  
                array[q->val+100]++;
                if(array[q->val+100]==1){
                    p->next=q;
                    p=q;
                } 
                    q=q->next;
            }//while
            p->next=NULL;
        }//if
		return head;
    }