代码随想录打卡第三天| 203.移除链表元素 707.设计链表 206.反转链表
2024-01-02 21:24:30
1.基本思想:为统一链表的删除结点操作,避免单独处理头结点,选择创造一个虚拟头结点shead。这样就统一了链表的删除逻辑,用一个变量p代替虚拟头结点进行遍历删除操作,最后用shead->next返回新链表头结点,记得释放虚拟头结点,下面给出代码:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val) {
typedef struct ListNode ListNode;
ListNode* p;
ListNode* temp;
ListNode* shead=(ListNode*)malloc(sizeof(ListNode));
shead->next=head;
p=shead;//用p代替shead进行遍历操作方便最后shead返回头结点
while(p->next!=NULL){
if(p->next->val==val){
temp=p->next;
p->next=temp->next;
free(temp);
}
else
p=p->next;
}
head=shead->next;
free(shead);
return head;
}
1.这题初看每一个小函数实现起来不难,但其实把所有函数的逻辑统一起来并不简单。踩了许多坑,比如obj其实是指向虚拟头结点的指针,并不是指向第一个元素的结点,因为初始链表可能为空但obj指针依然存在。(附:其它不易理解的地方见链表注释)
typedef struct MyLinkedList{//重定义结构体
int val;
struct MyLinkedList* next;
} MyLinkedList;
MyLinkedList* myLinkedListCreate() {//初始化结构体
MyLinkedList* head=(MyLinkedList*)malloc(sizeof(MyLinkedList));
head->next=NULL;
return head;
}
int myLinkedListGet(MyLinkedList* obj, int index) {
MyLinkedList *cur = obj->next;//obj表示虚拟头结点不含数据
for(int i=0;cur!=NULL;i++){//用cur表示obj的下一个结点,这样能使cur与i和index一一对应
if(i==index)//当i与index相等时cur就指向当前结点
return cur->val;
else
cur=cur->next;
}
return -1;
}
void myLinkedListAddAtHead(MyLinkedList* obj, int val) {//obj表示虚拟头结点
MyLinkedList* nhead=(MyLinkedList*)malloc(sizeof(MyLinkedList));
nhead->val=val;
nhead->next=obj->next;
obj->next=nhead;
}
void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
MyLinkedList* ntail=(MyLinkedList*)malloc(sizeof(MyLinkedList));
ntail->val=val;
ntail->next=NULL;
MyLinkedList *cur = obj;//用cur代替obj进行链表遍历,结束时cur就指向最后一个结点
while(cur->next!=NULL)
cur=cur->next;
cur->next=ntail;
}
void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
for(int i=0;obj!=NULL;i++){//当i与index相等时obj->next指向下标为index的结点
if(i==index){//而在下标为index的结点之前插入新结点,需要找到上一个结点也就是obj指向的结点
MyLinkedList* newnode = (MyLinkedList *)malloc(sizeof (MyLinkedList));
newnode->val=val;
newnode->next=obj->next;
obj->next=newnode;
return;
}
else
obj=obj->next;
}
}
void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
for(int i=0;obj!=NULL;i++){
if(i==index){//删除下标为index的结点也需要找到上一个结点才能操作
MyLinkedList*temp=obj->next;
if(temp!=NULL){
obj->next=temp->next;
free(temp);
}
return;
}
else
obj=obj->next;
}
}
void myLinkedListFree(MyLinkedList* obj) {
while(obj!=NULL){
MyLinkedList*temp=obj;
obj=obj->next;
free(temp);
}
}
/**
* Your MyLinkedList struct will be instantiated and called as such:
* MyLinkedList* obj = myLinkedListCreate();
* int param_1 = myLinkedListGet(obj, index);
* myLinkedListAddAtHead(obj, val);
* myLinkedListAddAtTail(obj, val);
* myLinkedListAddAtIndex(obj, index, val);
* myLinkedListDeleteAtIndex(obj, index);
* myLinkedListFree(obj);
*/
1.看到题目的第一反应是用408里面的头插法逆置单链表,很惭愧一下没有写出来。去看了讲解发现主流两种解法是双指针法和递归法(注:递归法是在双指针法的基础上完成的),看完两种解法后,第二次用头插法完成了逆置通过了测试。下给出三种解法的代码实现:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {//头插法逆置单链表
typedef struct ListNode ListNode;
ListNode* shead=(ListNode*)malloc(sizeof(ListNode));
ListNode* p;
ListNode* temp;
shead->next=NULL;创造一个虚拟头结点使链表整体处理逻辑一致、初始虚拟头结点指向NULL
while(head){//处理逻辑是每一次从现有链表摘下第一个结点插入虚拟头结点之后,达到逆置链表效果
temp=head->next;//用一个临时指针保留当前结点的下一个结点
head->next=shead->next;//逆置语句
shead->next=head;
head=temp;
}
head=shead->next;
free(shead);
return head;
}
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {//双指针法
typedef struct ListNode ListNode;
ListNode* cur,*pre;//分别用来保存当前结点和当前结点的前一个结点
pre=NULL;
cur=head;
while(cur){
ListNode* temp=cur->next;//用一个临时结点保存当前结点的下一个结点
cur->next=pre;//当前结点每次前移的时候都先让它指向前一个结点,达到逆置效果
pre=cur;//pre指针与cur指针前移开始下一次逆置
cur=temp;
}
return pre;//结束时,pre指向最后一个逆置的结点
}
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverse(struct ListNode* pre,struct ListNode* cur){//递归写法
if(cur==NULL)//递归终止条件
return pre;
struct ListNode*temp=cur->next;
cur->next=pre;
return reverse(cur,temp);//递归不结束时传入新的pre和cur的值
}
struct ListNode* reverseList(struct ListNode* head) {
return reverse(NULL,head);//初始pre与cur的位置
}
今日总结:上不来气了。
文章来源:https://blog.csdn.net/m0_72484482/article/details/135297088
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!