算法：有序链表的去重

LeetCode OJ Problem  ：Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,

Given 

1->1->2

, return 

1->2

.

Given 

1->1->2->3->3

, return 

1->2->3

.

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        //刷在研究生操蛋语文考试前夕
        if((head == NULL) || (head->next == NULL))
            return head;
        ListNode *p, *r, *temp;
        p = head;
        while(p)
        {
            while(p && (p->next) && (p->val != p->next->val))
                p = p->next;
            if((!p) || (!p->next))
                return head;
            while((p->next) && (p->val == p->next->val))
            {
                temp = p->next;
                r = temp->next;
                p->next = r;
                temp->next = NULL;
                delete temp;
            }
            
            //p = p->next;
        }
        
    }
};
           

LeetCode OJ Problem  ：Remove Duplicates from Sorted List II 

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,

Given 

1->2->3->3->4->4->5

, return 

1->2->5

.

Given 

1->1->1->2->3

, return 

2->3

.

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if((!head) || (!head->next))
            return head;
        ListNode *p, *pre_p, *r, *pre_r, *deleteHead, *deleEnd, *temp;
        deleteHead = deleEnd = new ListNode(0);//作为将要删除的链表的头结点
        pre_p = p = head;
        while(p && p->next)
        {
           if(p->val == p->next->val)
           {
               r = p->next;
               while((r != NULL) && (p->val == r->val)) 
               {
                   pre_r = r;
                   r = r->next;
               }
               deleEnd->next = p;
               deleEnd = pre_r;
               deleEnd->next = NULL;
               
                if(head == p)
                {
                    head = p = pre_p = r;
                }
                else
                {
                    p = r;
                    pre_p->next = p;
                }
           }
           else
           {
                pre_p = p;
                p = p->next;
           }
           
        }
        p = deleteHead;
        while(!p)
        {
            temp = p;
            p = p->next;
            delete temp;
            
        }
        return head;
        
    }
};