83.删除顺序链表中的重复元素[easy]

LeetCode 算法题停止更新，请移步至 GitHub。

题目地址

206.删除排序链表中的重复元素

题目描述

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

解题方法

1.直接法

把当前的节点值和下一个节点值作比较，如果相等，则直接删除下一个节点的值，这里注意，删除下一个节点后，不能直接移动当前指针到新的下一个节点，因为新的下一节点也有可能和当前节点值相等，而是要继续比较一次。注意边界条件，避免出现空指针错误。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == NULL || head -> next == NULL) 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;
    }
};

执行用时 : 20 ms, 在Remove Duplicates from Sorted List的C++提交中击败了95.99% 的用户

内存消耗 : 9.5 MB, 在Remove Duplicates from Sorted List的C++提交中击败了5.13% 的用户

时间复杂度：O(n)

空间复杂度：O(1)

2.哈希表

1. 使用一个哈希表来存储节点的值和节点，存储格式为 [node -> value : node]

2. 遍历当前节点时，先到哈希表中找到是否有一样的值，如果有，则需要删除当前节点。注意，这里的先决条件是有序链表，因此哈希表中可以存储前一个节点的值。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == NULL || head -> next == NULL) return head;
        
        unordered_map<int, ListNode *> map;
        ListNode *node = head;
        while (node) {
            if (map.find(node -> val) != map.end()) {
                ListNode *tmp = map[node -> val];
                tmp -> next = tmp -> next -> next;
            } else {
                map[node -> val] = node;
            }
            node = node -> next;
        }
        return head;
    }
};

执行用时 : 24 ms, 在Remove Duplicates from Sorted List的C++提交中击败了49.58% 的用户

内存消耗 : 10.2 MB, 在Remove Duplicates from Sorted List的C++提交中击败了5.13% 的用户

时间复杂度：O(n)

空间复杂度：O(n)