本文最后更新于 195 天前，其中的信息可能已经有所发展或是发生改变。
203.移除链表元素
初次尝试
class Solution
{
public:
ListNode *removeElements(ListNode *head, int val) // ListNode *是返回类型
{
ListNode *sentinelNode = new ListNode(0, head);
ListNode *cur = sentinelNode;
while (cur->next != NULL)
{
if (cur->next->val == val || cur->next->next != NULL)
{
ListNode *temp = cur->next;
cur->next = cur->next->next;
delete temp;
}
else if (cur->next->val == val || cur->next->next == NULL)
{
ListNode *temp = cur->next;
cur->next == NULL;
delete temp;
}
cur = cur->next;
}
return cur;
}
};
虽然加了哨兵结点,但是误判了循环终止的条件.
一开始我觉得最后一个节点就什么也不指向了,但实际上,最后一个节点指向了null.
代码实现
class Solution
{
public:
ListNode *removeElements(ListNode *head, int val) // ListNode *是返回类型
{
ListNode *sentinelNode = new ListNode(0, head);
ListNode *cur = sentinelNode;
while (cur->next != NULL)
{
if (cur->next->val == val)
{
ListNode *temp = cur->next;
cur->next = cur->next->next;
delete temp;
} else {
// 为什么要加else?假设删除的是最后一个节点,那么cur->next就指向null,如果不加else语句继续循环的话,cur就会更新为null,在while判断循环的时候cur->next的时候就会产生错误
cur = cur->next;
}
}
head = sentinelNode->next;
delete sentinelNode;
return head;
}
};
注意那个else语句!我个人觉得很容易忽略.
707.设计链表
因为网站上给的是单链表版本,所以我这里写的是双链表.
关于指针
sentinelNode是一个DList类型的指针,他在初始化的时候被指向了一个由new创建出来的对象
MyLinkedList()
{
sentinelNode = new DList(0);
sentinelNode->next = sentinelNode;
sentinelNode->prev = sentinelNode;
size = 0;
}
一开始看见这个语句我有点疑惑,为什么左边带*右边不带呢,别慌,我们来分析一下,首先我们知道sentinelNode被定义为一个指针,里面存放的是一个地址,右边的curNode也是一个指针,里面存放的也应该是一个地址,如果我们在左边用*sentinelNode的话,就把sentinelNode内存放地址位置的对象的值赋给curNode了,这显然是不对的.
DList *curNode = sentinelNode;
这种语句目的是在迭代curNode的时候不更改原有的链表,但是因为是指针,curNode又可以直接操作链表.
关于哨兵结点
我这里采用循环哨兵结点,只需要一个结点即可满足.
struct DList
{
int elem;
DList *next;
DList *prev;
DList(int elem) : elem(elem), next(nullptr), prev(nullptr){};
};
MyLinkedList()
{
sentinelNode = new DList(0);
sentinelNode->next = sentinelNode;
sentinelNode->prev = sentinelNode;
size = 0;
}
注意初始化的时候要将哨兵结点的头尾相接,不然在addHead和addTail方法里面可能会出现空指针.
我们来看一下我们的addHead和addTail方法
void addAtHead(int val)
{
DList *newNode = new DList(val);
DList *next = sentinelNode->next;
newNode->prev = sentinelNode;
newNode->next = next;
size++;
sentinelNode->next = newNode;
next->prev = newNode;
}
void addAtTail(int val)
{
DList *newNode = new DList(val);
DList *prev = sentinelNode->prev;
newNode->next = sentinelNode;
newNode->prev = prev;
size++;
sentinelNode->prev = newNode;
prev->next = newNode;
}
注意看这两句
DList *next = sentinelNode->next;
next->prev = newNode;
DList *prev = sentinelNode->prev;
prev->next = newNode;
如果初始化的时候没有首尾相接,那么sentinelNode->next和sentinelNode->prev就指向nullptr,那么在使用next->prev和prev->next就会出现空指针异常
代码实现
class MyLinkedList
{
public:
struct DList
{
int elem;
DList *next;
DList *prev;
DList(int elem) : elem(elem), next(nullptr), prev(nullptr){};
};
MyLinkedList()
{
sentinelNode = new DList(0);
sentinelNode->next = sentinelNode;
sentinelNode->prev = sentinelNode;
size = 0;
}
int get(int index)
{
if (index > (size - 1) || index < 0)
{
return -1;
}
int num;
int mid = size >> 1;
DList *curNode = sentinelNode;
if (index < mid)
{
for (int i = 0; i < index + 1; i++)
{
curNode = curNode->next;
}
}
else
{
for (int i = 0; i < size - index; i++)
{
curNode = curNode->prev;
}
}
num = curNode->elem;
return num;
}
void addAtHead(int val)
{
DList *newNode = new DList(val);
DList *next = sentinelNode->next;
newNode->prev = sentinelNode;
newNode->next = next;
size++;
sentinelNode->next = newNode;
next->prev = newNode;
}
void addAtTail(int val)
{
DList *newNode = new DList(val);
DList *prev = sentinelNode->prev;
newNode->next = sentinelNode;
newNode->prev = prev;
size++;
sentinelNode->prev = newNode;
prev->next = newNode;
}
void addAtIndex(int index, int val)
{
if (index > (size))
{
return;
}
if (index <= 0)
{
addAtHead(val);
return;
}
int num;
int mid = size >> 1;
DList *curNode = sentinelNode;
if (index < mid)
{
for (int i = 0; i < index; i++)
{
curNode = curNode->next;
}
DList *temp = curNode->next;
DList *newNode = new DList(val);
curNode->next = newNode;
temp->prev = newNode;
newNode->next = temp;
newNode->prev = curNode;
}
else
{
for (int i = 0; i < size - index; i++)
{
curNode = curNode->prev;
}
DList *temp = curNode->prev;
DList *newNode = new DList(val);
curNode->prev = newNode;
temp->next = newNode;
newNode->prev = temp;
newNode->next = curNode;
}
size++;
}
void deleteAtIndex(int index)
{
if (index > (size - 1) || index < 0)
{
return;
}
int num;
int mid = size >> 1;
DList *curNode = sentinelNode;
if (index < mid)
{
for (int i = 0; i < index; i++)
{
curNode = curNode->next;
}
DList *next = curNode->next->next;
curNode->next = next;
next->prev = curNode;
}
else
{
for (int i = 0; i < size - index - 1; i++)
{
curNode = curNode->prev;
}
DList *prev = curNode->prev->prev;
curNode->prev = prev;
prev->next = curNode;
}
size--;
}
private:
int size;
DList *sentinelNode;
};
206.反转链表
循环法
我的第一次尝试
class Solution
{
public:
ListNode *reverseList(ListNode *head)
{
ListNode *sentinelNode = new ListNode(0, head);
ListNode *prev = sentinelNode;
ListNode *cur = sentinelNode->next;
ListNode *temp = cur->next;
while (cur != NULL)
{
temp = cur->next;
cur->next = prev;
prev = cur;
cur = temp;
}
return prev;
}
};
假设传入的链表位1->2->3->4->5如果按照上面的写法,我们的初始链表就是0->1->2->3->4->5,在进行反转操作的时候,返回的值会多一个0
好奇怪我重新设置了一下prev和temp的初始化,又可以跑通了
我推测是因为完成反转链表操作之后,sentinelNode的值“0”为最后一位,没有NULL,所以导致错误.
class Solution
{
public:
ListNode *reverseList(ListNode *head)
{
ListNode *sentinelNode = new ListNode(0, head);
ListNode *prev = NULL;
ListNode *cur = sentinelNode->next;
ListNode *temp = NULL;
while (cur != NULL)
{
temp = cur->next;
cur->next = prev;
prev = cur;
cur = temp;
}
return prev;
}
};
这种方法也行
class Solution
{
public:
ListNode *reverseList(ListNode *head)
{
ListNode *prev = NULL;
ListNode *cur = head;
ListNode *temp;
while (cur != NULL)
{
temp = cur->next;
cur->next = prev;
prev = cur;
cur = temp;
}
return prev;
}
};
递归法
class Solution
{
public:
ListNode *reverse(ListNode *pre, ListNode *cur)
{
if (cur == NULL)
{
return pre;
}
ListNode *temp = cur->next;
cur->next = pre;
return reverse(cur, temp);
}
ListNode *reverseList(ListNode *head)
{
return reverse(NULL, head);
}
};
思考一下这两个声明的指针是什么意思.
ListNode *reverseList(ListNode *head){};
ListNode *reverse(ListNode *pre, ListNode *cur){};
这两个声明是定义一个==返回==类型为ListNode *的函数,为什么要用指针呢,因为这样就不必把整个数据复制一遍,而使用指针引用了数据.
