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

题目主要信息:

• 给定一个从小到大排好序的链表
• 删去链表中重复的元素，每个值只留下一个节点

具体思路:

既然相同的元素只留下一个，我们留下哪一个最好呢？当然是遇到的第一个元素了！因为第一个元素直接就与前面的链表节点连接好了，前面就不用管了，只需要跳过后面重复的元素，连接第一个不重复的元素就可以了，在链表中连接后面的元素总比连接前面的元素更方便嘛，因为不能逆序访问。

• step 1：判断链表是否为空链表，空链表不处理直接返回。
• step 2：使用一个指针遍历链表，如果指针当前节点与下一个节点的值相同，我们就跳过下一个节点，当前节点直接连接下个节点的后一位。
• step 3：如果当前节点与下一个节点值不同，继续往后遍历。
• step 4：循环过程中每次用到了两个节点值，要检查连续两个节点是否为空。

具体过程如下图所示：

代码实现:

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head == NULL) //空链表
            return NULL;
        ListNode* cur = head; //遍历指针
        while(cur != NULL && cur->next != NULL){ //指针当前和下一位不为空
            if(cur->val == cur->next->val) //如果当前与下一位相等则忽略下一位
                cur->next = cur->next->next;
            else //否则指针正常遍历
                cur = cur->next;
        }
        return head;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为链表长度，遍历一次链表
• 空间复杂度：$O(1)O(1)$，