1. 設計一個單連結清單
在連結清單類中實作這些功能：
get(index)：擷取連結清單中第 index 個節點的值。如果索引無效，則傳回-1。
addAtHead(val)：在連結清單的第一個元素之前添加一個值為 val 的節點。插入後，新節點将成為連結清單的第一個節點。
addAtTail(val)：将值為 val 的節點追加到連結清單的最後一個元素。
addAtIndex(index,val)：在連結清單中的第 index 個節點之前添加值為 val 的節點。如果 index 等于連結清單的長度，則該節點将附加到連結清單的末尾。如果 index 大于連結清單長度，則不會插入節點。如果index小于0，則在頭部插入節點。
deleteAtIndex(index)：如果索引 index 有效，則删除連結清單中的第 index 個節點。
來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/design-linked-list
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
class node
{
public:
int val;
node *next;
node(int v):val(v),next(NULL) {}
};
class MyLinkedList {
node *head, *tail;
int len;
public:
/** Initialize your data structure here. */
MyLinkedList() {
head = tail = NULL;
len = 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 >= len || index < 0)
return -1;
node *cur = head;
while(index--)
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 *h = new node(val);
h->next = head;
head = h;
if(len == 0)
tail = head;
++len;
}
/** Append a node of value val to the last element of the linked list. */
void addAtTail(int val) {
node *t = new node(val);
if(len == 0)
{
head = tail = t;
}
else
{
tail->next = t;
tail = t;
}
++len;
}
/** 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 == len)
addAtTail(val);
else if(index <= 0)
addAtHead(val);
else if(index > len)
return;
else
{
node *cur = head;
while(--index)
cur = cur->next;
node *newNode = new node(val);
newNode->next = cur->next;
cur->next = newNode;
++len;
}
}
/** Delete the index-th node in the linked list, if the index is valid. */
void deleteAtIndex(int index) {
if(index >= len || index < 0)
return;
--len;
node *virtualheadNode, *del, *cur;
virtualheadNode = new node(0);
virtualheadNode->next = head;
cur = virtualheadNode;
while(index--)
{
cur = cur->next;
}
del = cur->next;
cur->next = cur->next->next;
delete del;
head = virtualheadNode->next;
if(cur->next == NULL)
tail = cur;
delete virtualheadNode;
}
}; 複制
2. 雙向連結清單
class node
{
public:
int val;
node *next;
node *prev;
node(int v):val(v),next(NULL),prev(NULL) {}
};
class MyLinkedList {
node *head, *tail;
int len;
public:
/** Initialize your data structure here. */
MyLinkedList() {
head = tail = NULL;
len = 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 >= len || index < 0)
return -1;
node *cur = head;
while(index--)
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 *h = new node(val);
h->next = head;
head = h;
if(len == 0)
tail = head;
++len;
}
/** Append a node of value val to the last element of the linked list. */
void addAtTail(int val) {
node *t = new node(val);
if(len == 0)
{
head = tail = t;
}
else
{
tail->next = t;
t->prev = tail;
tail = t;
}
++len;
}
/** 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 == len)
addAtTail(val);
else if(index <= 0)
addAtHead(val);
else if(index > len)
return;
else
{
node *cur = head;
while(--index)
cur = cur->next;
node *newNode = new node(val);
newNode->next = cur->next;
newNode->prev = cur;
cur->next->prev = newNode;
cur->next = newNode;
++len;
}
}
/** Delete the index-th node in the linked list, if the index is valid. */
void deleteAtIndex(int index) {
if(index >= len || index < 0)
return;
--len;
node *virtualheadNode, *del, *cur;
virtualheadNode = new node(0);
virtualheadNode->next = head;
head->prev = virtualheadNode;
cur = virtualheadNode;
while(index--)
{
cur = cur->next;
}
del = cur->next;
cur->next = cur->next->next;
if(del->next)
del->next->prev = cur;
delete del;
head = virtualheadNode->next;
if(cur->next == NULL)
tail = cur;
delete virtualheadNode;
}
}; 複制