日野弥生：勉強しよう
LeetCode 707 - 设计链表
发表于2025年01月10日
单链表
结点类本身存储节点值和节点类型的下一个指针； 链表类则需要存储头指针；
注意get()函数需要从头指针开始遍历，而头指针没有指向任何数值，所以遍历次数应该是index+1 然而，addAtIndex()函数需要找到插入元素之前的指针，所以遍历次数是index。
struct LinkListNode {
int val;
LinkListNode *next;
LinkListNode(int _val) : val(_val), next(nullptr) {}
};
class MyLinkedList {
private:
int size=0;
ListNode* head=nullptr;
public:
MyLinkedList() {
head=new ListNode();
size=0;
}
int get(int index) {
if(index<0 || index>=size)
return -1;
ListNode* it=head;
for(int i=0;i<=index;i++)
{
it=it->next;
}
return it->val;
}
void addAtHead(int val) {
addAtIndex(0,val);
}
void addAtTail(int val) {
addAtIndex(size,val);
}
void addAtIndex(int index, int val) {
if(index>size)
return;
ListNode* prev=head;
for(int i=0;i<index;i++)
{
prev=prev->next;
}
ListNode *newAdd = new ListNode(val);
newAdd->next=prev->next;
prev->next=newAdd;
size++;
}
void deleteAtIndex(int index) {
if (index < 0 || index >= size)
return;
ListNode* prev=head;
for(int i=0;i<index;i++)
{
prev=prev->next;
}
ListNode* delPtr=prev->next;
prev->next=prev->next->next;
delete delPtr;
size--;
}
};双链表
双链表的结点类需要存储前指针和后指针； get和set类函数都需要判断所在位置处在链表结构的前半部分还是后半部分，此处需要注意从头遍历和从尾遍历的次数。
struct DLinkListNode {
int val;
DLinkListNode *prev, *next;
DLinkListNode(int _val) : val(_val), prev(nullptr), next(nullptr) {}
};
class MyLinkedList
{
private:
DLinkListNode* head=nullptr, *tail=nullptr;
int size=0;
public:
MyLinkedList()
{
head=new DLinkListNode(0);
tail=new DLinkListNode(0);
size=0;
head->next=tail;
tail->prev=head;
}
int get(int index)
{
if (index < 0 || index >= size)
return -1;
DLinkListNode* getPtr=nullptr;
if(index*2 < (size-1))
{
getPtr=head;
for (int i = 0; i <= index; i++) {
getPtr = getPtr->next;
}
}
else
{
getPtr=tail;
for (int i = 0; i < size - index; i++) {
getPtr = getPtr->prev;
}
}
return getPtr->val;
}
void addAtHead(int val) {
addAtIndex(0, val);
}
void addAtTail(int val) {
addAtIndex(size, val);
}
void addAtIndex(int index, int val)
{
if (index > size)
return;
DLinkListNode *pred, *succ;
if (index < size - index)
{
pred = head;
for (int i = 0; i < index; i++) {
pred = pred->next;
}
succ = pred->next;
} else {
succ = tail;
for (int i = 0; i < size - index; i++) {
succ = succ->prev;
}
pred = succ->prev;
}
size++;
DLinkListNode *toAdd = new DLinkListNode(val);
toAdd->prev = pred;
toAdd->next = succ;
pred->next = toAdd;
succ->prev = toAdd;
}
void deleteAtIndex(int index)
{
if (index < 0 || index >= size)
return;
DLinkListNode *pred, *succ;
if (index < size - index) {
pred = head;
for (int i = 0; i < index; i++) {
pred = pred->next;
}
succ = pred->next->next;
} else {
succ = tail;
for (int i = 0; i < size - index - 1; i++) {
succ = succ->prev;
}
pred = succ->prev->prev;
}
size--;
DLinkListNode *toDel = pred->next;
pred->next = succ;
succ->prev = pred;
delete toDel;
}
};