justExercise/RemoveDuplicatesFromSortedList82.cpp at master · studentBC/justExercise · GitHub

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
/**
 * 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)return head;
        ListNode*prev , *ptr = head;
        int previous , count = 0;
        for (ptr = head; ptr!=NULL; ptr= ptr->next) {
            count++;
        }
        bool* repeat = (bool*)calloc(count , sizeof(bool));
        if (repeat[0]) cout << " yes it is true" << endl;
        count = 0;ptr = head;
        while (ptr) {
            previous = ptr->val;
            ptr = ptr->next;
            if (ptr) {
                if (ptr->val == previous) {
                    repeat[count] = repeat[count+1]  = true;
                    cout << count << " , " << count+1 <<"    " ;
                }
            }
            count++;
        }
        ptr = head;count = 0;
        while (ptr) {
            if (!repeat[count]) {
                head = ptr;
                break;
            }
            ptr = ptr->next;
            count++;
        }
        cout << endl <<head->val << endl << count+1 << endl;
        prev = head;count++;
        for (ptr = head->next; ptr!=NULL; ptr= ptr->next) {
            if (!repeat[count]) {
                prev->next = ptr;
                prev = ptr;
            }
            count++;
        }
        prev = NULL;
        return head;
    }
};
//the fatest method
/**
 * 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 *dmy = new ListNode(0);
        dmy->next = head;

        ListNode *prev = dmy;

        while (prev->next) {

            ListNode *curr = prev->next, *p = curr->next;

            while (p && p->val == curr->val) {
                ListNode *tmp = p;
                p = p->next;
                delete tmp;
            }

            // p stops at diff node
            if (curr->next == p)
                prev = prev->next;
            else {
                prev->next = p;
                delete curr;
            }
        }

        return dmy->next;
    }
};