代码随想录打卡第三天| 203.移除链表元素 707.设计链表 206.反转链表

2024-01-02 21:24:30

203.移除链表元素

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;
}

707.设计链表

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);
*/

206.反转链表

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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。