Day3 链表
链表也是一种很重要的数据结构,链表的优势是空间不必连续,分配比较自由,缺点是不支持随机访问,想要获取链表中间的某个元素,必须要从头遍历。
LeetCode 203.移除链表元素【虚拟头结点】
移除链表中的某个元素很简单,只需要把这个节点前一个节点的next指针指向这个节点后面一个元素即可。但是头结点是没有前一个节点的,此时我们有两种做法,一种是特判头结点,如果头结点元素满条件,则将头指针不断后移,其余方法不变,另一种方法是创造一个虚拟头结点,让头结点在删除时的特性与其余节点一致,而头结点的前驱就是我们创造的这个dummyhead。
解法1:头结点特判
头结点特判有一点需要注意:开头对头结点的判断要用while而不是if,因为头结点之后如果存在连续相等的值,在头结点删除后新的头结点仍满足条件,则需要全部删除。
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
while(head!=NULL && head->val==val){
ListNode* tmp=head;
head=head->next;
delete tmp;
}
ListNode* cur=head;
while(cur!=NULL && cur->next!=NULL){
if(cur->next->val==val){
ListNode* tmp=cur->next;
cur->next=cur->next->next;
delete tmp;
}
else cur=cur->next;
}
return head;
}
};
解法2:虚拟头结点
这里是我的写法,其实需要在中间的判断中用临时变量获取p->next,然后delete掉,清理内存,这里没有写,以后删除需要养成良好的习惯。
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummy=new ListNode(0,head);
ListNode* p=dummy;
while(p->next!=NULL){
if(p->next->val==val){
p->next=p->next->next;
}
else p=p->next;
}
return dummy->next;
}
};
LeetCode 707.设计链表【链表基础】
最考验基本功的一集,如果你仍然对链表操作有疑问,那么请回到这一题,它能解答你对所有链表基本操作的疑问。
这道题我在一开始做的时候用了数组模拟链表逃课AC了,如果题目并没有强制要求用严格的链表结构实现,有时候可以用数组模拟,这样相当于用空间换了代码复杂度。
解法1:数组模拟
class MyLinkedList {
public:
int head,e[1010],ne[1010],idx,siz;
MyLinkedList() {
head=-1;
idx=0;
siz=0;
}
int get(int index) {
if(index>=siz || index<0)
return -1;
int i=head;
while(index--) i=ne[i];
return e[i];
}
void addAtHead(int val) {
e[idx]=val;
ne[idx]=head;
head=idx++;
siz++;
}
void addAtTail(int val) {
addAtIndex(siz,val);
}
void addAtIndex(int index, int val) {
if(index>siz) return;
if(index<=0){
addAtHead(val);
return;
}
int i=head;
while(--index) i=ne[i];
e[idx]=val;
ne[idx]=ne[i];
ne[i]=idx++;
siz++;
}
void deleteAtIndex(int index) {
if(index>=siz || index<0) return;
if(index==0){
head=ne[head];
siz--;
return;
}
int i=head;
while(--index) i=ne[i];
ne[i]=ne[ne[i]];
siz--;
}
};
解法2:链表结构
如果向上一题一样,题目已经要求使用链表结构,那就不能投机取巧了,要把基本操作好好了解一下。
class MyLinkedList {
public:
struct LinkedNode{
int val;
LinkedNode* next;
LinkedNode(int val):val(val),next(nullptr){}
};
MyLinkedList() {
dummyHead=new LinkedNode(0);
siz=0;
}
int get(int index) {
if(index>(siz-1) || index<0) return -1;
LinkedNode* cur=dummyHead->next;
while(index--) cur=cur->next;
return cur->val;
}
void addAtHead(int val) {
LinkedNode* newNode=new LinkedNode(val);
newNode->next=dummyHead->next;
dummyHead->next=newNode;
siz++;
}
void addAtTail(int val) {
LinkedNode* newNode=new LinkedNode(val);
LinkedNode* cur=dummyHead;
while(cur->next!=NULL) cur=cur->next;
cur->next=newNode;
siz++;
}
void addAtIndex(int index, int val) {
if(index>siz) return;
if(index<0) index=0;
LinkedNode* newNode=new LinkedNode(val);
LinkedNode* cur=dummyHead;
while(index--) cur=cur->next;
newNode->next=cur->next;
cur->next=newNode;
siz++;
}
void deleteAtIndex(int index) {
if(index>=siz || index<0) return;
LinkedNode* cur=dummyHead;
while(index--) cur=cur->next;
LinkedNode* tmp=cur->next;
cur->next=cur->next->next;
delete tmp;
siz--;
}
private:
int siz;
LinkedNode* dummyHead;
};
LeetCode 206.反转链表【双指针/递归】
反转链表也是一个非常经典的问题,它要求我们每走一步就要改变两个节点之间next指针的位置,这里有双指针法和递归法两种,得好好研究一下。
解法1:双指针
双指针解法是想法比较基础的解法,就是用一前一后两个指针,把后面的指针转到前面来。
细节:第一步cur移动前要用tmp保存cur->next,否则会丢失下一节点。
每次移动指针时,先动pre,再动cur,否则两个指针会断连。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* cur=head;
ListNode* pre=NULL;
ListNode* tmp;
while(cur){
tmp=cur->next;
cur->next=pre;
pre=cur;
cur=tmp;
}
return pre;
}
};
解法2:递归
递归解法的本质还是双指针算法,只不过把双指针向前移动的过程转化为reverse函数中替换形参的过程,不过代码确实很简洁,当做思维扩展学了。
class Solution {
public:
ListNode* reverse(ListNode* cur,ListNode* pre){
if(cur==NULL) return pre;
ListNode* tmp=cur->next;
cur->next=pre;
return reverse(tmp,cur);
}
ListNode* reverseList(ListNode* head) {
return reverse(head,NULL);
}
};
今日收获很多啊,对链表的理解更深了。