Remove Duplicate

发表于 | 分类于

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

题目描述1：

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

例子：

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

解题思路：

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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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)。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
    }
};

题目描述2：

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

例子：

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

解题思路：

主要的难点在于头结点情况的处理，这边用了虚拟头结点来处理删掉头节点的情况。然后不断用flag遍历代表当前要判断是否重复的节点，分成重复和不重复两种情况处理。注意在找下一个节点和当前节点是否相同的时候需要加上head->next。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * 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) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        //定义虚拟头节点方便删除头节点
        ListNode* pre = dummy;
        while(head){
            ListNode* flag = head;
            //flag为当前判断是否重复的节点
            while(head->next && head->next->val == head->val){
                head = head->next;
                //一直遍历到和flag节点的值不同为止
            }
            if (head == flag){
                pre = flag;
                head = flag->next;
                //下一个节点和上一个节点不重复的情况
            }else{
                pre->next = head->next;
                head = head->next;
                //重复的情况
            }
        }
        return dummy->next;
    }
};