题目描述:

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

 

方法一: 从头开始遍历链表,当遇到相同元素则跳过该元素,指向下一节点

struct ListNode* removeElements(struct ListNode* head, int val) {if(head == NULL)return NULL;struct ListNode* cur = head;struct ListNode* prev = NULL;while(cur){//如果当前节点是需要删除的节点if(cur->val == val){//首先保存下一个节点struct ListNode* next = cur->next;//如果删除的为头节点，更新头节点//否则让当前节点的前趋节点链接next节点if(prev == NULL){head = cur->next;}else{prev->next =next;  }//释放当前节点，让cur指向nextfree(cur);cur = next;}else{//如果cur不是需要删除的节点，则更新prev,curprev = cur;cur = cur->next;}}return head;
}

这里要特别注意一种情况,当结点就为要删除的元素时,记得要更新头节点,由于我们会释放掉结点,不更新头结点会返回一个野指针

方法二: 定义一个新链表,依次尾插与val不同的结点

struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* newnode=NULL,*tail=NULL;struct ListNode* cur=head;while(cur){if(cur->val!=val){//插入第一个结点要特殊判断if(tail==NULL){newnode=tail=cur;}else{tail->next=cur;tail=tail->next;}cur=cur->next;}else{//删除当前节点,cur向后走struct ListNode* tmp=cur;cur=cur->next;free(tmp);}}if(tail)tail->next=NULL;return newnode;
}

 本题中,tail始终指向新链表的末尾,便于尾插操作,插入元素时要先判断是否为第一个元素,即当尾指针tail为空时,新链表为空,这时需要将newnode和tail指向尾插的第一个结点,最后记得把尾指针置空,防止其指向野指针