题目

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

示例 1:

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

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

解题代码与测试

//
// Created by tannzh on 2020/8/20.
//

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

示例 1:

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

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

 */

#include <iostream>
#include <vector>

using std::vector;
using vecIter = vector<int>::iterator;

//Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        for (ListNode *cur = head; cur && cur->next; ){
            if (cur->val == cur->next->val){
                ListNode *del = cur->next;
                cur->next = del->next;
                delete del;
            }
            else cur = cur->next;
        }
        return head;
    }
};

ListNode *createLinkedList(vecIter beg, vecIter end)
{
    ListNode *head = beg == end ? NULL : new ListNode(*beg++);
    for (ListNode *cur = head; beg != end; cur = cur->next)
        cur->next = new ListNode(*beg++);
    return head;
}

void printAndClear(ListNode *head)
{
    while (head)
    {
        std::cout << head->val;
        if (head->next) std::cout << "->";
        ListNode *del = head;
        head = head->next;
        delete del;
    }
    std::cout << std::endl;
}

int main()
{
    vector<int> vec = {1,1,2};
    vector<int> vec1 = {1,1,2,3,3};

    ListNode *head = createLinkedList(vec.begin(), vec.end());
    ListNode *head1 = createLinkedList(vec1.begin(), vec1.end());

    Solution s;
    ListNode *res = s.deleteDuplicates(head);
    ListNode *res1 = s.deleteDuplicates(head1);

    printAndClear(res);
    printAndClear(res1);

    return 0;
}

解题思路分析

这题目还是很基础, 本不需要说什么, 但后来看了 Discuss 之后, 发现大家还关注内存回收的问题. 删去的节点, 应该被 delete. 这是对的. 我开始却给自动忽略了.

这造成的问题就是, 测试主函数中, 每一个节点必须要 new 出来, 而不能仅仅像以前一样, 声明一个局部对象. (当然, 这样做就是为了避免回收内存, 图简单.) 否则你 delete 的时候必然会造成内存错误的.