@[TOC]

写在前面

本篇为本人学习链表的过程中遇到的典型OJ题，于是整理出来分享思路和便于后续重新学习，每个标题均可跳转至对应习题，大多为Leetcode

链表OJ调试技巧

Leetcode中只能看到函数体，不能看到链表的具体情况，因此调试存在困难，自己搭建链表又过于繁琐，这里介绍一种很方便的链表调试技巧

==原理如下==

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

struct ListNode
{
   
   
    int val;
    struct ListNode* next;
};

int main()
{
   
   
    struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    assert(n1);
    struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    assert(n2);
    struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    assert(n3);
    struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
    assert(n4);
    struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
    assert(n5);

    n1->val = 1;
    n2->val = 2;
    n3->val = 3;
    n4->val = 4;
    n5->val = 5;

    n1->next = n2;
    n2->next = n3;
    n3->next = n4;
    n4->next = n5;
    n5->next = NULL;
}

我们只需要创建出每一个节点，接着把这些节点都连在一起，手动创建一个链表，链表中需要多少个元素自己搭建，这样可以便于调试，解决OJ中遇到的问题~~

介绍完调试的方法，正式总结链表中的OJ题目

移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点

1.遍历，是val的删掉

一种暴力解决的方法，图示如下

==代码实现如下==

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


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

2.遍历链表，把不是val的拿下来尾插

图解过程如下：

==代码如下所示==

struct ListNode* removeElements(struct ListNode* head, int val)
{
   
   
    struct ListNode* cur=head;
    struct ListNode* newnode = NULL;
    struct ListNode* tail = NULL;
    while(cur)
    {
   
   
        if(cur->val!=val)
        {
   
   
            if(tail==NULL)
            {
   
   
                newnode=tail=cur;
            }
            else
            {
   
   
                tail->next=cur;
                tail=tail->next;
            }

            cur=cur->next;
        }
        else
        {
   
   
            struct ListNode* del=cur;
            cur=cur->next;
            free(del);
        }
    }

    if(tail)
        tail->next=NULL;

    return newnode;
}