单链表OJ题：移除链表元素（力扣）

解法一：带头节点的新链表

解法二：不带头节点的新指向关系链表

总结

这是一道简单的力扣题目，关于解法的话，这里提供了二种思路，重点解释前两种，还有一种思路好想，但是时间复杂度为O(n^2) ，提供的这两种时间复杂度为O(n)，所以，我们以解题的代码量少，时间最优选择提供的这两种的解法。

解法一：带头节点的新链表

这里只所以要带头节点，是因为带头节点可以给我们的解题上带来一些方便，在总结里面我们会重点比较带头节点和不带头节点解题上的区别。

带头节点时，我们需要申请一个头节点，头节点的作用是用来占位（最后我们需要返回的是头节点的下一个节点地址），然后，我们遍历原链表，将原链表中节点的val值不为6的节点依次尾插在头节点的后面，最后，将最后的节点的next域置为NULL，我们得到一个新链表，返回头节点的下一个节点的地址，就是我们的答案。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {ListNode* newNodeHead = (ListNode*)malloc(sizeof(ListNode));  //创建新链表的头节点newNodeHead->val = 0, newNodeHead->next = NULL;ListNode* newHead,*newTail;newHeadHead = newTail = newNode;     //初始化头指针和尾指针指向新链表的第一个节点//遍历原链表while(head){if(head->val != val){newTail->next = head;       //找到符合的值就插入到新链表的后面newTail = newTail->next;     //尾指针后移}head = head->next;      //不断后移指针} newTail->next = NULL;return newHeadHead->next;
}

我们举个例子，一开始，我们申请一头节点，头节点的next域为NULL,我们要遍历原链表，将原链表中val值不为6的节点连接在newNodeHead后面

修改完之后，节点的关系如图所示，原链表的节点指向被改变，尾节点的next域为NULL

这里需要注意：

1、尾指针始终要指向头节点后面要尾插的节点，也就是指向新链表的最后一个节点，当原链表查找结束的时候，要把尾指针的next置为NULL。（一方面，防止当新链表中的最后一个节点是原链表的中间节点的时候，尾节点的next域不为NULL，便会访问原链表中的这个中间节点后面的节点，也就会访问到其中的节点中不满足val条件的节点，另一方面，当第一个节点为NULL时，我们需要返回的是头节点的next域，所以这时要把该指针置为NULL）

2、返回的是头节点的next指针，也就是头节点的下一个节点。

解法二：不带头节点的新指向关系链表

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
typedef struct ListNode  ListNode;
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {if(head==NULL){return NULL;}ListNode * newHead,*newTail;   //创建新的链表newHead = newTail = NULL;//遍历链表ListNode * pcur = head;   //创建指向头节点的指针，便于遍历while(pcur){if(pcur->val != val){//找值不为val的节点，将这个节点添加到新链表中if(newHead == NULL){newHead = newTail = pcur;}else{newTail->next = pcur;newTail = newTail->next;    //尾指针向后移动}}pcur = pcur->next;    //pucr 往后遍历}if(newTail != NULL){newTail->next = NULL;}return newHead;}
};

从这里，可以看出，我们不带头节点的解法代码量增加了许多，总体思路分为下面的几步：

1、我们创建头指针指向新链表的第一个节点和尾指针指向新链表的最后一个节点。

2、我们遍历原链表，查找节点值不为val的节点，然后，我们把节点尾插到新链表中。

3、插入的时候分两种情况，一种是头指针为NULL，此时要将头指针和尾指针都指向这个节点当新链表的第一个节点。

4、当头指针不为NULL时，要把节点插入到尾指针指向节点的后面

5、原链表查找结束后，将尾节点的next域置为NULL.（注意，此时的尾指针可能没有指向原链表的节点，也就是此时newTail尾NULL，这时我们不需要将尾节点的next域置为NULL，不然会报错）

总结

这里，因为解法一有头节点的存在，我们在实现尾插的时候，就不需要考虑插入第一个节点时头指针和尾指针指向的两种情况，直接在头节点后面插入满足条件的节点就行。第二个方便的地方就是，我们在查找完成后，对尾指针指向的节点置为NULL的时候，当有头节点的时候，尾指针可以直接置为NULL，因为此次的尾指针指向的是头节点，但是，当尾指针指向的节点不存在的时候，这个时候就不能执行将newTail置为NULL的操作了。