Remove Duplicate

Remove Duplicate(删除链表中的重复节点)

题目描述：

给定一个无序链表的头节点，删除其中出现重复的节点。

例子：

1->2->3->3->4->4-2->1->1->NULL。删除其中的重复节点后得到1->2->3->4->NULL。

解题思路：

首先我们第一个想法是记录下当前遍历过程中已经出现过的节点，这样在不断的遍历过程中只要是已经出现过的节点就直接删除。所以利用哈希表的思路。用一个哈希表记录遍历过程中得到的节点，然后每次遍历判断是否在表中，不在的情况加入表；在的情况下就直接删除当前节点。

代码如下：

class removeRepeatValue1{
public:
    ListNode* removeRepeatValue(ListNode* head){
        if (head == NULL || head->next == NULL)
            return head;
        std::set<int> num; // 构建哈希表
        ListNode* pre = head;
        ListNode* cur = head->next;
        num.insert(pre->val); 
        //第一个节点肯定不是重复的，从第二个节点开始遍历
        while(cur != NULL){
            if (num.find(cur->val) == num.end()){
                num.insert(cur->val);
                cur = cur->next;
                pre = pre->next;//如果不在哈希表中
            }
            else{
                pre->next = cur->next;
                cur = pre->next; // 如果在则删除当前节点
            }
        }
        return head;
    }                   //同样删除链表中的节点需要注意保持前一个节点
};

解题思路2：

当然哈希表直观简单，但是利用了较多的空间。所以利用下面这种方法可以减少空间复杂度，同样时间复杂度会较高。

主要的想法是，首先遍历第一个节点，然后找到链表中所有和该节点相同的节点，删除掉，然后遍历下一个节点。时间复杂度为O(N^2)，空间复杂度为O(1)。

代码如下：

class removeRepeatValue2{
public:
    ListNode* removeRepeatValue(ListNode* head) {
        if (head == NULL || head->next == NULL)
            return head;
        ListNode *step = head;
        while (step != NULL) {
            int flag = step->val; //记录当前节点的值
            ListNode *cur = step->next;
            ListNode *pre = step;
            while (cur != NULL) {
                if (cur->val == flag) {
                    pre->next = cur->next;
                    cur = pre->next;
                } else {
                    cur = cur->next;
                    pre = pre->next;
                }  // 如果有和当前节点值相同的，删除掉
            }
            step = step->next; // 遍历下一个节点
        }
        return head;
    }
};