-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathsolution.cpp
More file actions
126 lines (106 loc) · 2.99 KB
/
Copy pathsolution.cpp
File metadata and controls
126 lines (106 loc) · 2.99 KB
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
//
// Created by Gatsby on 2023/11/23.
//
#include "solution.h"
#include <vector>
#include <math.h>
#include <iostream>
using namespace std;
typedef struct Node {
int data;
Node *next;
} Node;
class solution {
public:
/*
static Node *remove_duplicate(Node *head, int n) {
vector<int> nums(n + 1);
Node *cur = head;
nums.push_back(abs(head->data));
while (cur->next != nullptr) {
int data = cur->next->data;
data = abs(data);
if (nums[data] == 1) {
cur->next = cur->next->next;
} else {
nums[data] = 1;
}
cur = cur->next;
}
return head;
}
错误答案，因为有可能存在多个连续的同样的数字
*/
/*
正确解法还是要两个节点，
static Node *remove_duplicate(Node *head, int n) {
vector<int> nums(n + 1);
Node *prev = head;
Node *curr = head->next;
while (curr != nullptr) {
int data = abs(curr->data);
if (nums[data] == 1) {
prev->next = curr->next;
Node *temp = curr;
// prev此时不需要移动
curr = curr->next;
delete temp;
} else {
nums[data] = 1;
// 关键的一个条件判断，prev是先不动的，只有确定没问题了才移动prev
prev = prev->next;
curr = curr->next;
}
}
return head;
}
*/
// 则上述代码的修改方法也已经很明了，再确保正确之前，cur不应该移动
// 其实一个指针也是足够的
static Node *remove_duplicate(Node *head, int n) {
vector<int> nums(n + 1);
Node *cur = head;
nums.push_back(abs(head->data));
while (cur->next != nullptr) {
int data = cur->next->data;
data = abs(data);
if (nums[data] == 1) {
cur->next = cur->next->next;
} else {
nums[data] = 1;
cur = cur->next;
}
}
return head;
}
static Node *create_linked_list(const vector<int> &nums) {
Node *head = new Node();
Node *tail = head;
for (int num: nums) {
Node *node = new Node();
node->data = num;
node->next = nullptr;
tail->next = node;
tail = tail->next;
}
return head;
}
};
int main() {
vector<int> nums{21, -15, -15, -15, -7, 15, 15};
Node *head = solution::create_linked_list(nums);
Node *curr = head->next;
cout << head->data;
while (curr) {
cout << "->" << curr->data;
curr = curr->next;
}
cout << "-----" << endl;
Node *new_head = solution::remove_duplicate(head, 32);
curr = head->next;
cout << new_head->data;
while (curr) {
cout << "->" << curr->data;
curr = curr->next;
}
}