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

题目：删除有序链表中重复的元素

描述：给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
例如：给出的链表为1→2→3→3→4→4→5，返回1→2→5。
给出的链表为1→1→1→2→3，返回2→3。

示例1：输入：{1,2,2}，返回值：{1}

解法一：

思路分析：可以利用双指针法，首先我们可以设置一个newhead对象，pre = newhead，cur = head，在已知head的情况下，我们开始循环判断cur对象，设置循环条件为cur ->next不为空，判断cur->val是否等于cur->next->val，如果等于就将count的值累加（其中count的值为链表中的重复累加元素的个数和），当有重复的情况发生，就令pre->next = cur->next，count = 0，删除该元素，始终进行如下判断，如果没有重复，就将pre链表的值变为现在cur链表的值，递归条件为cur = cur - next。

实例分析：给出的链表为1→2→3→3→4→4→5

1、首先设定newhead对象，pre对象，cur对象和count的值为0。

2、根据程序设定，令nexhead = {0,1,2,3,3,4,4,5}，pre: {0,1,2,3,3,4,4,5}，cur: {1,2,3,3,4,4,5}，判断cur ->next是否为空，不为空，判断cur->val是否等于cur->next->val，不等于，则说明第一个与第二个不为重复元素，则将pre与cur进行同步，将cur设定为cur - next。

3、再次循环，继续进行判断。

4、当发现重复的元素，将count的值累加，count = 1，在进行一次循环后将pre->next = cur->next，count = 0，如此pre = {2,4,4,5}，cur = {4,4,5}。

5、通过上述重复进行判断，最终输出结果。

具体C++代码为：

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */
 
class Solution {
public:
    /**
     *
     * @param head ListNode类
     * @return ListNode类
     */
    ListNode* deleteDuplicates(ListNode* head) {
        // write code here
        ListNode* newhead = new ListNode(0);//设置一个初始链表
        newhead->next = head;//将head链表添加到newhead中
        ListNode* pre = newhead;
        ListNode* cur = head;
        int count = 0;//设置重复次数
        while(cur != NULL && cur->next != NULL){//判断条件
            if(cur->val == cur->next->val){//如果按照顺序，值相等
                cur->next = cur->next->next;//删除该元素
                count++;//将count次数加一再次进行判断
            }
            else{
                if(count > 0){
                    pre->next = cur->next;//将该元素值全部删除
                    count = 0;
                }
                else
                    pre = cur;
                cur = cur->next;//递归条件
            }
        }
        if(count > 0)//存在比如{1，2，2}，因为删除，所以上述循环条件不进行判断，在此额外进行判断
            pre->next = cur->next;
        return newhead->next;
    }
};

将所有链表的值进行判断，除了当倒数第二个值与最后一个值相等的话，其他情况下，需要遍历链表中的全部元素，故时间复杂度为O(N)，空间复杂度为O(N)。

解法二：

思路分析：使用递归的方法去求解，当head后面存在值且与head的值相等的话，那么就一直向后找，直到找到不相等的值为止，然后对后面的那个结点进行递归，删除前面重复的结点，如果head的值与head.next的值不相等的话，那么就递归后面的结点，最后返回head变量。

实例分析：给出的链表为1→2→3→3→4→4→5

具体java代码为：

import java.util.*;
 
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */
 
public class Solution {
    /**
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null){
            return null;
        }
        if(head.next != null && head.val == head.next.val){//发现有重复值
                while(head.next != null && head.val == head.next.val){
                    head = head.next;//删除
            }
            return deleteDuplicates(head.next);//把与删除的那个结点相同的结点也进行删除
        }
        head.next = deleteDuplicates(head.next);//当没有发现重复值的情况，就一直进行递归操作
        return head;
    }
}

递归操作，将链表元素值进行递归，重复递归导致其时间复杂度为O(N)，因为没有占用任何的内存空间，所以其空间复杂度为O(1)。