problem
solution
option 1 - Linked List
- be carefull edge case
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
70struct Node{
int val ;
Node *next;
Node(int val){
this->val = val;
this->next= nullptr;
}
};
class MyLinkedList {
private:
int size;
Node *head;
public:
MyLinkedList() {
size = 0;
head = new Node(-1);
}
int get(int index) {
if(index > size-1) return -1;
Node *p = head->next;
while(index--)p=p->next;
return p->val;
}
void addAtHead(int val) {
size++;
Node *node = new Node(val);
Node *post = head->next;
node->next = post;
head->next = node;
}
void addAtTail(int val) {
size++;
Node * p= head->next;
// size == 0
if(!p){
head->next = new Node(val);
}
else{
while(p->next) p=p->next;
p->next = new Node(val);
}
}
void addAtIndex(int index, int val) {
// be careful, index == size-1, equal append()
if(index > size) return;
size++;
Node *node = new Node(val);
Node *p = head->next, *pre = head;
while(index--) {
pre = p;
p=p->next;
}
pre->next = node;
node->next = p;
}
void deleteAtIndex(int index) {
if(index > size-1) return;
size--;
Node *p = head->next, *pre = head;
while(index--) {
pre = p;
p=p->next;
}
pre->next= p->next;
}
};add tail pointer
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
79class Node{
public:
int val;
Node *next;
Node(int val){
this->val = val;
this->next = nullptr;
}
};
class MyLinkedList {
private:
Node *head, *tail;
int size ;
public:
MyLinkedList() {
size = 0;
head = new Node(-1);
tail = new Node(-1);
head->next = tail;
}
int get(int index) {
if(index > size-1) return -1;
Node * p = head->next;
while(index--) p=p->next;
return p->val;
}
void addAtHead(int val) {
size++;
Node *post = head->next;
Node * node = new Node(val);
head->next = node;
node->next = post;
}
void addAtTail(int val) {
size++;
Node * p = head->next;
Node * node = new Node(val);
// size ==0
if(p==tail){
head->next = node;
node->next = tail;
}
else{
while(p->next!=tail) p=p->next;
p->next = node;
node->next = tail;
}
}
void addAtIndex(int index, int val) {
if(index > size ) return;
size++;
Node *p = head->next, *pre = head;
while(index--) {
pre = p;
p=p->next;
}
Node * node = new Node(val);
pre->next = node;
node->next = p;
}
void deleteAtIndex(int index) {
if(index > size -1) return;
size--;
Node *p = head->next, *pre = head;
while(index--) {
pre = p;
p=p->next;
}
pre->next = p->next;
}
};option 2 - Double Linked List
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
87class Node{
public:
int val;
Node *next, *prev;
Node(int val){
this->val = val;
this->next = nullptr;
this->prev = nullptr;
}
};
class MyLinkedList {
private:
Node *head, *tail;
int size ;
public:
MyLinkedList() {
size = 0;
head = new Node(-1);
tail = new Node(-1);
head->next = tail;
tail->prev = head;
}
int get(int index) {
if(index > size-1) return -1;
Node * p = head->next;
while(index--) p=p->next;
return p->val;
}
void addAtHead(int val) {
size++;
Node *post = head->next;
Node * node = new Node(val);
node->prev = head;
node->next = post;
head->next = node;
post->prev = node;
}
void addAtTail(int val) {
size++;
Node * p = head->next;
Node * node = new Node(val);
// head->next == prev;
if(p==tail){
node->next = tail;
tail->prev = node;
node->prev = head;
head->next = node;
}
else{
while(p->next!=tail) p=p->next;
p->next = node;
node->prev = p;
node->next = tail;
tail->prev = node;
}
}
void addAtIndex(int index, int val) {
if(index > size ) return;
size++;
Node *p = head->next, *pre = head;
while(index--) {
pre = p;
p=p->next;
}
Node * node = new Node(val);
pre->next = node;
node->prev = pre;
node->next = p;
p->prev = node;
}
void deleteAtIndex(int index) {
if(index > size -1) return;
size--;
Node *p = head->next, *pre = head;
while(index--) {
pre = p;
p=p->next;
}
pre->next = p->next;
pre->next->prev = pre;
}
};