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

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的位置
}

今日总结：上不来气了。