题解 | #删除有序链表中重复的元素-II#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* deleteDuplicates(ListNode* head) {
        // write code here
        if(!head || !head->next)
            return head;
        ListNode *res = new ListNode(0);
        res->next = head;
        ListNode *curr = res;
        //每次都是2个节点判断
        while(curr->next && curr->next->next)
        {
            //存在重复节点
            if(curr->next->val == curr->next->next->val)
            {
                //记录第一个重复节点的值
                int temp = curr->next->val;
                //循环遍历后续节点的值，并与记录的节点值比较，相同则逐个删除
                while(curr->next && curr->next->val == temp)
                    curr->next = curr->next->next;
            }
            else
                curr = curr->next;//本轮不存在重复节点，值链表指针后移
        }
        return res->next;
    }
};

具体做法：

• step 1：给链表前加上表头，方便可能的话删除第一个节点。
• step 2：遍历链表，每次比较相邻两个节点，如果遇到了两个相邻节点相同，则新开内循环将这一段所有的相同都遍历过去。
• step 3：在step 2中这一连串相同的节点前的节点直接连上后续第一个不相同值的节点。
• step 4：返回时去掉添加的表头。