数据结构---经典链表OJ

乐观学习，乐观生活，才能不断前进啊！！！

我的主页：optimistic_chen
我的专栏：c语言
点击主页：optimistic_chen和专栏：c语言，
创作不易，大佬们点赞鼓励下吧~

文章目录

移除链表元素
反转链表
完结

移除链表元素

移除链表元素—力扣
在这里插入图片描述
第一种思路：简单粗暴，直接遍历一次链表，把val所在的节点释放掉。

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    ListNode *cure=head;
    ListNode* prev=head;
    
    while(cure)
    {
      if(cure->val==val){
        if(head==cure){
            head=cure->next;
        }else{
        prev->next=cure->next;
        }
        
      cure=cure->next;
      }
      else{
        prev=cure;
        cure=prev->next;
      }
    }
    return head;
}

第二种思路：创建新链表，再遍历原链表，找到不为 val 的节点尾插到新链表。


typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    if (head == NULL)
        return NULL;

    //创建一个新链表
    ListNode* newHead, * newTail;
    newHead = newTail = NULL;
    ListNode* pcur = head;

    //遍历原链表
    while (pcur)
    {
    //找不为val的节点尾插
        if (pcur->val != val)
        {
            //链表为空
            if (newHead == NULL)
            {
                newHead = newTail = pcur;
            }
            //链表不为空
            else
            {
                //有一个节点以上
                newTail->next = pcur;
                newTail = newTail->next;
            }
        }

        pcur = pcur->next;
    }

    if (newTail)//若原链表为空，判断newTail是否为空
        newTail->next = NULL;

    return newHead;

}

反转链表

反转链表—力扣
在这里插入图片描述
头插法：创建一个新链表，遍历原链表，依次取下原链表的每一个节点头插到新链表中。


typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {

    if (head == NULL)
        return NULL;

    ListNode* newHead, * newTail;
    newHead = newTail = NULL;
    ListNode* pcur = head;

    //一个一个拿下来头插
    while (pcur)
    {
        ListNode* next = pcur->next;
        pcur->next = newHead;
        newHead = pcur;
        pcur = next;
    }

    return newHead;
}

反转指针法：定义三个变量 n1，n2，n3，根据它们的指向关系进行迭代。

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {

    if (head == NULL)
        return NULL;

    ListNode* n1, * n2, * n3;
    n1 = NULL, n2 = head, n3 = n2->next;

    while (n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;

        if (n3)//别忘记判断 n3 ，防止对空指针解引用
            n3 = n3->next;
    }

    return n1;
}