leetcode 83. 删除排序链表中的重复元素(C++)

爱被打了一巴掌 2023-07-12 05:29 20阅读 0赞

# 题目 #

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

输入: 1->1->2
    输出: 1->2

示例 2:

输入: 1->1->2->3->3
    输出: 1->2->3

来源：[83. 删除排序链表中的重复元素 - 力扣（LeetCode）][83. _ - _LeetCode]  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

# 双指针法 #

*  定义两个指针，  
    p1负责遍历整个原链表，p2比对两个指针指向节点的值  
    在两者不相等时将p1指向的节点接到自身指向节点的后面

代码如下：

class Solution { 
    public:
        ListNode* deleteDuplicates(ListNode* head) { 
            if(!head || !head->next)
                return head;
            ListNode* myhead = new ListNode(0);
            myhead->next = head;
            ListNode* node = head->next;
            while(node)
            { 
                if(node->val != head->val)
                {     
                    head->next = node;
                    head = head->next;
                }
                node = node->next;
            }
            head->next = NULL;
            return myhead->next;
        }
    };

结果：  
![在这里插入图片描述][20200308023627103.png]

# 直接法 #

*  若当前节点的值与下一个节点的值一样，就跳过下一个节点

代码如下：

class Solution { 
    public:
        ListNode* deleteDuplicates(ListNode* head) { 
            if(!head || !head->next)
                return head;
            ListNode* node = head;
            while(node && node->next)
            { 
                if(node->val == node->next->val) 
                    node->next = node->next->next;
                else 
                    node = node->next;
            }
            return head;
        }
    };

结果：  
![在这里插入图片描述][20200308024614538.png]

[83. _ - _LeetCode]: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list
[20200308023627103.png]: https://img-blog.csdnimg.cn/20200308023627103.png
[20200308024614538.png]: https://img-blog.csdnimg.cn/20200308024614538.png