您现在的位置是：首页 >学无止境 >代码随想录算法训练营第三天 | 203.移除链表元素，707.设计链表，206.反转链表网站首页学无止境

203. 移除链表元素
正确运行的代码如下：

truct ListNode* removeElements(struct ListNode* head, int val){
    while (head && head->val == val){
        head = head->next;
    }

    struct ListNode * cur = head;

    while (cur && cur->next){
        // printf("cur->val = %d
", cur->val);
        while (cur->next && cur->next->val == val){
            cur->next = cur->next->next;
        }
        cur = cur ->next;
    }

    return head;
}

或者通过创建一个虚拟头节点。

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode * dummyHead = (struct ListNode *)malloc(sizeof(struct ListNode));
    dummyHead->next = head;

    struct ListNode * cur = dummyHead;

    while (cur->next){
        if (cur->next->val == val){
            cur->next = cur->next->next;
        }
        else {
            cur = cur->next;
        }
    }

    return dummyHead->next;
}

以下是错误代码，不知道为什么超出时间限制。我通过打印运行结果，初步认为是无法判断链表结束。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 
struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode * pHead = NULL, * p = head, * q;

    while (p && p->val == val){
        p = p->next;
    }
    pHead = p;
    q = pHead;

    if (q){
        while (p){
            if (p->val != val){
                q->next = p;
                q = q->next;
            }
            p = p->next;
        }
    }

    return pHead;
}

707. 设计链表
这道题目包含了链表的基本操作，按照代码随想录的视频，设置了虚拟头节点来进行操作。

区分相关概念：
首节点：链表的第一个有效节点。
尾节点：最后一个有效节点。
头节点：链表的第一个有效节点之前的那个节点，头节点并不存放有效数据。加头节点的目的主要是为了方便对链表的操作。
头指针：指向头节点的指针变量。
尾指针：指向尾节点的指针变量。

为什么在遍历链表的时候要定义一个指针来遍历，而不是直接操作头指针？
这是因为我们要操作完链表之后要返回头节点，如果直接操作头节点的话，那头节点的值都被修改了，那么如何返回链表的头节点呢？所以要定义一个临时指针指向头节点进行遍历。

对于这道题目而言，一定要明白第n个节点在哪里，以及如何对链表进行插入数据。
注意链表中的所有节点下标从 0 开始。
正确运行的代码如下。

typedef struct {
    int val;
    struct MyLinkedList * next;
} MyLinkedList;


MyLinkedList* myLinkedListCreate() {
    MyLinkedList * dummyhead = (MyLinkedList *) malloc (sizeof(MyLinkedList));
    dummyhead->val = 0;
    dummyhead->next = NULL;

    return dummyhead;
}

int myLinkedListGet(MyLinkedList* obj, int index) {
    MyLinkedList * cur = obj->next;
    while (index-- && cur){
        cur = cur->next;
    }

    if (cur){
        return cur->val;
    }
    return -1;
}

void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
    MyLinkedList * q = (MyLinkedList *) malloc (sizeof(MyLinkedList));
    q->val = val;
    q->next = obj->next;
    obj->next = q;
}

void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
    MyLinkedList * q = (MyLinkedList *) malloc (sizeof(MyLinkedList));
    q->val = val;
    q->next = NULL;

    MyLinkedList * cur = obj;
    while (cur->next){
        cur = cur->next;
    }

    cur->next = q;
}

void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
    MyLinkedList * cur = obj;
    while (index-- && cur){
        cur = cur->next;
    }

    MyLinkedList * q = (MyLinkedList *) malloc (sizeof(MyLinkedList));
    q->val = val;
    q->next = NULL;

    if (cur){
        q->next = cur->next;
        cur->next = q;
    }
}

void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
    MyLinkedList * cur = obj;
    MyLinkedList * q;
    while (index--){
        cur = cur->next;
    }

    if (cur && cur->next){
        q = cur->next;
        cur->next = q->next;
    }
    
}

void myLinkedListFree(MyLinkedList* obj) {
    while (obj){
        MyLinkedList * q = obj;
        obj = obj->next;
        free(q);
    }
}

以下是错误代码，还没有想明白是为什么。

typedef struct Node{ //定义链表的节点的结构体
    int val; //数据域
    struct Node * next; //指针域
}Node, * pNode;

typedef struct { //定义链表的结构体
    pNode dummyhead; //头指针
    int len; //链表长度
} MyLinkedList;


MyLinkedList* myLinkedListCreate() {
    MyLinkedList * list = (MyLinkedList *) malloc (sizeof(MyLinkedList));
    list->dummyhead = NULL;
    list->len = 0;

    return list;
}

int myLinkedListGet(MyLinkedList* obj, int index) {
    if (index < 0 || index >= obj->len){
        return -1;
    }
    pNode cur = obj->dummyhead;
    while (index--){
        cur = cur->next;
    }
    return cur->val;
}

void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
    pNode q = (pNode) malloc (sizeof(Node));
    q->val = val;
    q->next = NULL;

    pNode cur = obj->dummyhead;
    if (cur){
        q->next = cur->next;
        cur->next = q;
        obj->len++;
    }
}

void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
    pNode q = (pNode) malloc (sizeof(Node));
    q->val = val;
    q->next = NULL;

    pNode cur = obj->dummyhead;
    while (cur && cur->next){
        cur = cur->next;
    }
    if (cur){
        cur->next = q;
        obj->len++;
    }
}

void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
    if (index < 0 || index > obj->len){
        return;
    }
    else if (index == 0){
        myLinkedListAddAtHead(obj, val);
    }
    else if (index == obj->len){
        myLinkedListAddAtTail(obj, val);
    }
    else {
        pNode q = (pNode) malloc (sizeof(Node));
        q->val = val;
        q->next = NULL;

        pNode cur = obj->dummyhead;
        while (index--){
            cur = cur->next;
        }

        q->next = cur->next;
        cur->next = q;
        obj->len++;
    }
}

void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
    if (index >= 0 && index < obj->len){
        pNode cur = obj->dummyhead;
        while (index--){
            cur = cur->next;
        }

        cur->next = cur->next->next;
        obj->len--;
    }
}

void myLinkedListFree(MyLinkedList* obj) {
    pNode q, cur = obj->dummyhead;

    while (obj->len--){
        q = cur->next;
        free(q);
        cur = cur->next;
    }
}

/**
 * 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. 反转链表
注意掌握双指针解法以及递归写法。

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode * pre = NULL, * cur = head; //初始化变量

    while (cur){
        struct ListNode * tmp = cur->next; //临时变量保存
        cur->next = pre; //反转
        pre = cur; //更新变量
        cur = tmp;
    }

    return pre; //返回头节点
}

struct ListNode * reverse(struct ListNode * cur, struct ListNode * pre){
    if (!cur){
        return pre;
    }
    struct ListNode * tmp = cur->next;
    cur->next = pre;
    return reverse(tmp, cur);
}

struct ListNode* reverseList(struct ListNode* head){
    return reverse(head, NULL);
}

继续加油~