Problem: 707. 设计链表
思路
链表的结构和链表的基本操作
脑瘫的错误
1.要注意范围判断
在get函数中范围是if (index > (_size - 1) || index < 0) return -1;不能超过最大索引
在addIndex中范围是if (index > _size) return;
可以是_size也就是最大索引加一,代表添加到末尾
2.总是忘记修改完链表后更新长度 size
Code
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
| class MyLinkedList {
public:
typedef struct LinkedNode {
int val;
LinkedNode* next;
LinkedNode(int val) :val(val), next(nullptr) {}
} LinkedNode;
MyLinkedList() {
_dummyHead = new LinkedNode(0);
_size = 0;
}
int get(int index) {
if (index > (_size - 1) || index < 0) return -1;
LinkedNode* current = _dummyHead->next;
while (index--) {
current = current->next;
}
return current->val;
}
void addAtHead(int val) {
LinkedNode* newNode = new LinkedNode(val);
newNode->next = _dummyHead->next;
_dummyHead->next = newNode;
_size++;
}
void addAtTail(int val) {
LinkedNode* current = _dummyHead;
LinkedNode* newNode = new LinkedNode(val);
while (current->next != nullptr) {
current = current->next;
}
current->next = newNode;
_size++;
}
void addAtIndex(int index, int val) {
if (index > _size) return;
if (index < 0) index = 0;
LinkedNode* current = _dummyHead;
LinkedNode* newNode = new LinkedNode(val);
while (index--) {
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
_size++;
}
void deleteAtIndex(int index) {
if (index >= _size) return;
LinkedNode* current = _dummyHead;
while (index--) {
current = current->next;
}
LinkedNode* p = current->next;
current->next = current->next->next;
delete p;
p = nullptr;
_size--;
}
void printLinkedList() {
LinkedNode* cur = _dummyHead;
while (cur->next != nullptr) {
cout << cur->next->val << " ";
cur = cur->next;
}
cout << endl;
}
private:
int _size;
LinkedNode* _dummyHead;
};
|