Leetcode No.83 Remove Duplicates from Sorted List移除有序数组中的重复元素(c++实现）

1. 题目

1.1 英文题目

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

1.2 中文题目

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

1.3输入输出

输入	输出
head = [1,1,2]	[1,2]
head = [1,1,2,3,3]	[1,2,3]

1.4 约束条件

• The number of nodes in the list is in the range [0, 300].
• -100 <= Node.val <= 100
• The list is guaranteed to be sorted in ascending order.

2. 分析

2.1 自己的算法

该算法逻辑不太清晰
代码如下：

class Solution {
 public:
     ListNode* deleteDuplicates(ListNode* head) {
         if (head == nullptr || head->next == nullptr) {
             return head;
         }
         ListNode* ptr = head;
         ListNode ansHead(0);
         ListNode* ans = &ansHead;
         while (ptr != nullptr) {
             ListNode* nextNode = ptr->next;
             if (nextNode != nullptr && nextNode->val == ptr->val) {
                 ptr->next = nextNode->next;
                 if (ptr->next == nullptr || ptr->next->val != ptr->val) {
                     ans->next = ptr;
                     ans = ans->next;
                 }
             }
             else {
                 ans->next = ptr;
                 ans = ans->next;
             }
             ptr = ptr->next;
         }
         return ansHead.next;
     }
 };

参考：https://leetcode.com/problems/merge-two-sorted-lists/discuss/9714/14-line-clean-C%2B%2B-Solution

2.2 大牛算法

该算法不仅代码简洁，而且还避免了内存泄漏的问题。
代码如下：

class Solution {
 public:
     ListNode* deleteDuplicates(ListNode* head) {
         ListNode* cur = head;
         while (cur != nullptr && cur->next != nullptr) {
             if (cur->val == cur->next->val) {
                 ListNode* tmp = cur->next;
                 cur->next = cur->next->next;
                 delete tmp;//删除重复节点，从而避免内存泄漏问题
             }
             else {
                 cur = cur->next;
             }
         }
         return head;
     }
 };

参考：https://leetcode.com/problems/remove-duplicates-from-sorted-list/discuss/1223275/Good-code-without-memory-leak-C%2B%2B-Ez-to-understnad