【Leetcode】删除链表中的重复元素

清疚 2022-10-12 05:53 175阅读 0赞

## 一、题目 ##

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，
    使每个元素只出现一次。返回同样按升序排列的结果链表。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 1]

## 二、解析 ##

对于此题，我的解题步骤如下：

1.  创建两个指针pre、curr，分别表示历史指针、当前指针。
2.  从链表的首位置开始，移动curr一步，并与pre的值相比较。
3.  如果相同，则跳过中间指针，将pre指向curr->next。但此时不更新pre，因为还需确定下一个元素是否与pre相同； 如果不同，则跟新pre。
4.  重复2、3步骤。

## 三、实现 ##

以上思路，通过C++实现如下：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */
    class Solution { 
    public:
        ListNode* deleteDuplicates(ListNode* head) { 
            ListNode* curr = head;
            ListNode* pre = curr;
            while(curr != nullptr)
            { 
               curr = curr -> next;
               if(curr != nullptr && curr->val == pre->val) //前后值一样
               { 
                   pre->next = curr->next; //跳过重复的节点
               }
               else
               { 
                   pre = curr; // 如果不是重复，则更新pre
               }
            }
            return head;
        }
    };

提交结果如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70]: /images/20221005/eaf7faf7f6ee4ce6abf73ce763a7e57a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 1]: /images/20221005/c4c294fdd6df4e1da5a2f2b6ae0d0934.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 2]: /images/20221005/7a5816b4bac14550be82362cbd79e803.png