Original Version
// Definition for singly-linked list.
struct SinglyListNode {
int val;
SinglyListNode *next;
SinglyListNode(int x) : val(x), next(NULL) {}
};
class MyLinkedList {
private:
SinglyListNode *head;
public:
/** Initialize your data structure here. */
MyLinkedList() {
head = NULL;
}
/** Helper function to return the index-th node in the linked list. */
SinglyListNode* getNode(int index) {
SinglyListNode *cur = head;
for (int i = 0; i < index && cur; ++i) {
cur = cur->next;
}
return cur;
}
/** Helper function to return the last node in the linked list. */
SinglyListNode* getTail() {
SinglyListNode *cur = head;
while (cur && cur->next) {
cur = cur->next;
}
return cur;
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
int get(int index) {
SinglyListNode *cur = getNode(index);
return cur == NULL ? -1 : cur->val;
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
void addAtHead(int val) {
SinglyListNode *cur = new SinglyListNode(val);
cur->next = head;
head = cur;
return;
}
/** Append a node of value val to the last element of the linked list. */
void addAtTail(int val) {
if (head == NULL) {
addAtHead(val);
return;
}
SinglyListNode *prev = getTail();
SinglyListNode *cur = new SinglyListNode(val);
prev->next = cur;
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
void addAtIndex(int index, int val) {
if (index == 0) {
addAtHead(val);
return;
}
SinglyListNode *prev = getNode(index - 1);
if (prev == NULL) {
return;
}
SinglyListNode *cur = new SinglyListNode(val);
SinglyListNode *next = prev->next;
cur->next = next;
prev->next = cur;
}
/** Delete the index-th node in the linked list, if the index is valid. */
void deleteAtIndex(int index) {
SinglyListNode *cur = getNode(index);
if (cur == NULL) {
return;
}
SinglyListNode *prev = getNode(index - 1);
SinglyListNode *next = cur->next;
if (prev) {
prev->next = next;
} else {
// modify head when deleting the first node.
head = next;
}
}
};
1. Initiate a new linked list: represent a linked list using the head node.
// Definition for singly-linked list.
struct SinglyListNode {
int val;
SinglyListNode *next;
SinglyListNode(int x) : val(x), next(NULL) {}
};
class MyLinkedList {
private:
SinglyListNode *head;
public:
/** Initialize your data structure here. */
MyLinkedList() {
head = NULL;
}
};
2. Traverse the linked list to get element by index.
/** Helper function to return the index-th node in the linked list. */
SinglyListNode* getNode(int index) {
SinglyListNode *cur = head;
for (int i = 0; i < index && cur; ++i) {
cur = cur->next;
}
return cur;
}
/** Helper function to return the last node in the linked list. */
SinglyListNode* getTail() {
SinglyListNode *cur = head;
while (cur && cur->next) {
cur = cur->next;
}
return cur;
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
int get(int index) {
SinglyListNode *cur = getNode(index);
return cur == NULL ? -1 : cur->val;
}
3. Add a new node.
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
void addAtHead(int val) {
SinglyListNode *cur = new SinglyListNode(val);
cur->next = head;
head = cur;
return;
}
/** Append a node of value val to the last element of the linked list. */
void addAtTail(int val) {
if (head == NULL) {
addAtHead(val);
return;
}
SinglyListNode *prev = getTail();
SinglyListNode *cur = new SinglyListNode(val);
prev->next = cur;
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
void addAtIndex(int index, int val) {
if (index == 0) {
addAtHead(val);
return;
}
SinglyListNode *prev = getNode(index - 1);
if (prev == NULL) {
return;
}
SinglyListNode *cur = new SinglyListNode(val);
SinglyListNode *next = prev->next;
cur->next = next;
prev->next = cur;
}
It is worth noting that we have to get the(index - 1)th node or the last node before we add the new node (except adding at the head) and it takesO(N)time to get a node by index, where N is the length of the linked list. It is different from adding a new node after a given node.
4. Delete a node.
/** Delete the index-th node in the linked list, if the index is valid. */
void deleteAtIndex(int index) {
SinglyListNode *cur = getNode(index);
if (cur == NULL) {
return;
}
SinglyListNode *prev = getNode(index - 1);
SinglyListNode *next = cur->next;
if (prev) {
prev->next = next;
} else {
// modify head when deleting the first node.
head = next;
}
}
Similar to the add operation, it takesO(N)time to get the node by the index which is different from deleting a given node. However, even if we already get the node we want to delete, we still have to traverse to get its previous node.
Tail Version
struct SinglyListNode {
int val;
SinglyListNode *next;
SinglyListNode(int x) : val(x), next(NULL) {}
};
class MyLinkedList {
private:
SinglyListNode *head;
SinglyListNode *tail;
public:
/** Initialize your data structure here. */
MyLinkedList() {
head = NULL;
}
/** Helper function to return the index-th node in the linked list. */
SinglyListNode* getNode(int index) {
SinglyListNode *cur = head;
for (int i = 0; i < index && cur; ++i) {
cur = cur->next;
}
return cur;
}
/** Helper function to return the last node in the linked list. */
SinglyListNode* getTail() {
SinglyListNode *cur = head;
while (cur && cur->next) {
cur = cur->next;
}
return cur;
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
int get(int index) {
SinglyListNode *cur = getNode(index);
return cur == NULL ? -1 : cur->val;
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
void addAtHead(int val) {
SinglyListNode *cur = new SinglyListNode(val);
//cur->next = head;
//head = cur;
//return;
if (head == NULL) {
tail = cur;
}
cur->next = head;
head = cur;
//traverse(head, "addAtHead");
}
/** Append a node of value val to the last element of the linked list. */
void addAtTail(int val) {
if (head == NULL) {
addAtHead(val);
return;
}
//SinglyListNode *prev = getTail();
SinglyListNode *cur = new SinglyListNode(val);
//prev->next = cur;
tail->next = cur;
tail = cur;
//traverse(head, "addAtTail");
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
void addAtIndex(int index, int val) {
if (index == 0) {
addAtHead(val);
return;
}
SinglyListNode *prev = getNode(index - 1);
if (prev == NULL) {
return;
} else if (prev == tail) {
addAtTail(val);
return;
}
SinglyListNode *cur = new SinglyListNode(val);
SinglyListNode *next = prev->next;
cur->next = next;
prev->next = cur;
//traverse(head, "addAtIndex");
}
// delete front
void deleteFront() {
SinglyListNode *old = head;
if (old) {
head = head->next;
delete(old);
}
}
/** Delete the index-th node in the linked list, if the index is valid. */
void deleteAtIndex(int index) {
SinglyListNode *cur = getNode(index);
if (cur == NULL) {
return;
} else if (cur == tail) {
remove_end();
return;
}
SinglyListNode *prev = getNode(index - 1);
SinglyListNode *next = cur->next;
if (prev) {
prev->next = next;
} else {
// modify head when deleting the first node.
head = next;
}
}
void remove_end() {
if (head == NULL) {
cout << "empty" << endl;
return;
} else if (head->next == NULL) {
cout << "One node" << endl;
SinglyListNode *curr = head;
// bug: destructor error if delete the last node
// head = head->next;
head = NULL;
delete(curr);
return;
} else {
SinglyListNode *curr = head->next;
SinglyListNode *prev = head;
while (curr != tail) {
curr = curr->next;
prev = prev->next;
}
delete(curr);
tail = prev;
prev->next = NULL;
}
}
// traverse linked list
void traverse(SinglyListNode* head, string msg) {
while (head) {
cout << head->val << ' ';
head = head->next;
}
cout << msg << endl;
}
void traverse(SinglyListNode* head, string msg, int val) {
while (head) {
cout << head->val << ' ';
head = head->next;
}
cout << msg << val << endl;
}
};
Size Version
Tail & Size Version
Bug Verison
class MyLinkedList {
private:
struct Node {
int val;
Node* next;
Node* prev;
Node() {}
Node(int x): val(x), next(nullptr), prev(nullptr) {}
Node(int x, Node* nextp, Node* prevp): val(x), next(nextp), prev(prevp) {}
};
Node* head;
Node* tail;
int size;
public:
/** Initialize your data structure here. */
MyLinkedList() {
head = nullptr;
tail = nullptr;
size = 0;
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
int get(int index) {
if (index < 0 || index >= size) return -1;
Node* cur = head;
for (int i = 0; i < index; ++i) {
cur = cur->next;
}
return cur->val;
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
void addAtHead(int val) {
Node* cur = new Node(val);
if (head != nullptr) {
//head->next->prev = cur;
//cur->next = head->next;
//cur->pre = nullptr;
head->prev = cur;
cur->next = head;
cur->prev = nullptr;
} else {
tail = cur;
}
size++;
head = cur;
}
/** Append a node of value val to the last element of the linked list. */
void addAtTail(int val) {
Node* cur = new Node(val);
if (tail == nullptr) {
head = cur;
} else {
tail->next = cur;
cur->prev = tail;
}
size++;
tail = cur;
travese(head, "addTail");
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
void addAtIndex(int index, int val) {
travese(head, "addAtIndex");
cout << "size: " << size << " index: " << index << endl;
if (index == size) {
addAtTail(val);
return;
} else if (index > size) {
return;
} else {
Node* prevPtr = head;
for (int i = 0; i < index - 1; ++i) {
prevPtr = prevPtr->next;
}
Node* nextPtr = prevPtr->next;
Node* curPtr = new Node(val);
curPtr->next = nextPtr;
curPtr->prev = prevPtr;
nextPtr->prev = curPtr;
prevPtr->next = curPtr;
}
size++;
}
/** Delete the index-th node in the linked list, if the index is valid. */
void deleteAtIndex(int index) {
if (index < 0 || index >= size) return;
Node* curPtr = head;
for (int i = 0; i < index; ++i) {
curPtr = curPtr->next;
}
curPtr->prev->next = curPtr->next;
size--;
}
// traverse linked list
void travese(Node* head, string msg) {
while (head) {
cout << head->val << ' ';
head = head->next;
}
cout << msg << endl;
}
};
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList obj = new MyLinkedList();
* int param_1 = obj.get(index);
* obj.addAtHead(val);
* obj.addAtTail(val);
* obj.addAtIndex(index,val);
* obj.deleteAtIndex(index);
*/
Ref 1: head & size
class MyLinkedList {
public:
/** Initialize your data structure here. */
ListNode* head;
int size;
MyLinkedList(): head(nullptr), size(0) {}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
int get(int index) {
if (index >= this->size) return -1;
ListNode *p = this->head;
while (index--) { p = p->next; }
return p->val;
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
void addAtHead(int val) {
ListNode* new_node = new ListNode(val);
new_node->next = this->head;
this->head = new_node;
this->size++;
// this->print();
}
/** Append a node of value val to the last element of the linked list. */
void addAtTail(int val) {
if (this->size == 0) {
this->head = new ListNode(val);
this->size++;
return;
}
ListNode *p = this->head;
for (int i = this->size - 1; i > 0; --i) { p = p->next; }
p->next = new ListNode(val);
this->size++;
// this->print();
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
void addAtIndex(int index, int val) {
if (index > this->size) return;
if (index == this->size) { this->addAtTail(val); return; }
if (index == 0) { this->addAtHead(val); return; }
ListNode *p = this->head;
while (--index) { p = p->next; }
ListNode* new_node = new ListNode(val);
new_node->next = p->next;
p->next = new_node;
this->size++;
// this->print();
}
/** Delete the index-th node in the linked list, if the index is valid. */
void deleteAtIndex(int index) {
if (index >= this->size) return;
if (index == 0) {
ListNode *tmp = this->head;
this->head = this->head->next;
delete tmp;
this->size--;
return;
}
ListNode *p = this->head;
while (--index) { p = p->next; }
ListNode *tmp = p->next;
p->next = p->next->next;
delete tmp;
this->size--;
// this->print();
}
void print() {
ListNode *p = this->head;
cout << this->size << ": ";
while (p != nullptr) {
cout << p->val << "->";
p = p->next;
}
cout << endl;
}
};
Ref 2 : head, tail, size
class MyLinkedList {
private:
struct Node {
int val;
Node* next;
Node* prev;
Node() {}
Node(int x): val(x), next(nullptr), prev(nullptr) {}
Node(int x, Node* nextp, Node* prevp): val(x), next(nextp), prev(prevp) {}
};
Node* head;
Node* tail;
int size;
public:
/** Initialize your data structure here. */
MyLinkedList() {
head = nullptr;
tail = nullptr;
size = 0;
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
int get(int index) {
if (index < 0 || index >= size) return -1;
Node* cur = head;
for (int i = 0; i < index; ++i) {
cur = cur->next;
}
return cur->val;
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
void addAtHead(int val) {
Node* cur = new Node(val);
if (head != nullptr) {
//head->next->prev = cur;
//cur->next = head->next;
//cur->pre = nullptr;
head->prev = cur;
cur->next = head;
cur->prev = nullptr;
} else {
tail = cur;
}
size++;
head = cur;
}
/** Append a node of value val to the last element of the linked list. */
void addAtTail(int val) {
Node* cur = new Node(val);
if (tail == nullptr) {
head = cur;
} else {
tail->next = cur;
cur->prev = tail;
}
size++;
tail = cur;
travese(head, "addTail");
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
void addAtIndex(int index, int val) {
travese(head, "addAtIndex");
cout << "size: " << size << " index: " << index << endl;
if (index == size) {
addAtTail(val);
return;
} else if (index > size) {
return;
} else {
Node* prevPtr = head;
for (int i = 0; i < index - 1; ++i) {
prevPtr = prevPtr->next;
}
Node* nextPtr = prevPtr->next;
Node* curPtr = new Node(val);
curPtr->next = nextPtr;
curPtr->prev = prevPtr;
nextPtr->prev = curPtr;
prevPtr->next = curPtr;
}
size++;
}
/** Delete the index-th node in the linked list, if the index is valid. */
void deleteAtIndex(int index) {
if (index < 0 || index >= size) return;
Node* curPtr = head;
for (int i = 0; i < index; ++i) {
curPtr = curPtr->next;
}
curPtr->prev->next = curPtr->next;
size--;
}
// traverse linked list
void travese(Node* head, string msg) {
while (head) {
cout << head->val << ' ';
head = head->next;
}
cout << msg << endl;
}
};