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

描述
        删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次
例如：
给出的链表为1→1→2,返回1→2.
给出的链表为1→1→2→3→3,返回1→2→3.
示例1
输入：{1,1,2}
返回值：{1,2}

方法一：递归求解
核心思想：
        采用递归的思想求解。每次递归则需要比较并删除重复的元素。本次的思想跟递归逆置链表很像，唯一的不同就是处理逻辑不同。删除重复链表的处理逻辑是每次都要删除当前节点（如果当前节点与下一个节点相同时候）

核心代码：

ListNode* deleteDuplicates(ListNode* head) {
    if (head == nullptr || head->next == nullptr)    //节点不存在或者只有一个节点时，递归结束
        return head;
    head->next = deleteDuplicates(head->next);      //递归体，每次递归从下一个节点开始
    if (head->val == head->next->val)     //比较当前元素和下一个元素的值是否相等，相等则直接删除当前节点
        head = head->next;            //head指针指向下一个节点，表明当前节点丢失，已经不再属于这个链表
    return head;                //返回本次递归的结果
}

复杂度分析：
        递归n次，因此时间复杂度为O(N)。而每次递归都需要一个额外的变量保存，因此空间复杂度为O(N)
时间复杂度O(n)
空间复杂度O(n)

方法二：遍历删除
核心思想：
        遍历链表，并判断当前节点值是否与下一个节点值相等。当前节点值与下一个节点值相等则直接删除下一个节点值；否则指针继续后移，直到遍历完成。
边界条件：空链表或者只有一个节点的链表直接返回
循环条件：当前节点存在下一个节点时（因为每次循环都需要将当前节点与下一个节点相比较）

图解：

核心代码：

ListNode* deleteDuplicates(ListNode* head) {
    if (!head || head->next == nullptr)    //空链表或者只有一个节点的链表直接返回         
        return head;

    ListNode* cur = head;     //引入一个当前指针指向链表的头结点
    while (cur->next) {
        if (cur->val == cur->next->val)      //判断当前节点是否与下一个节点的值相等，相等则直接删除下一个节点
            cur->next = cur->next->next;
        else                 //当前节点与下一个节点的值不相等，则直接滑动指针
            cur = cur->next;
    }
    return head;
}

复杂度分析：
        代码循环遍历链表，循环次数为链表的长度，因此该方法的时间复杂度为O(N)。由于没有采用额外的空间，因此空间复杂度为O(1)
时间复杂度O(n)
空间复杂度O(1)