链表删除指定元素算法

我们只需要分情况理清楚就很简单

在算法分析的时候记清楚自己的思路是最重要的

只要链表里有一个元素与给定的元素不相同  第一次与给定元素不相同的节点就为头节点

1：改变头节点

2：不改变头节点
List deleList(List p,int val){

List r=p;

List head=NULL;

while(r ){

-------if(r->data==val){   //删除指定元素我分为两种情况 删除了头节点和 没有删除头节点

-------------if(p->data == val){//只要头节点所在的元素与val相等再回执行这条语句

-------------p=p->next; //第一个与val不相等的节点为头节点   聊表重要的就是头指针

-------------free( r);

-------------r=p;

-------------}

------else{

-------------head->next=r->next;

-------------free(r );

-------------r=head->next;  //

-------------}

}

-------else{

-------------head=r; //记录要删除节点的头一个节点

-------------r=r->next;

-------------}

}

return p;

}

本段代码实现了
1 新建链表
2  输出链表
3 删除链表中的指定元素
#include <stdio.h>
#include <stdlib.h>
#include<malloc.h>
#include "test1.h"

/*
创建一个结构体
*/
typedef struct Node {
	int data;//数据
	struct Node *next;//下一个结点的指针
}Node;
int count = 0;//记录链表的长度

Node *InitList() {
	Node *head;//定义头指针
	Node *q, *p;//定义两个结构体指针用于后面迭代
	head = (Node *)malloc(sizeof(Node));
	q = head;
	while (1)
	{
		count++;
		p = (Node *)malloc(sizeof(Node));
		printf("请输入第%d个数: (如需结束输入0):   ", count);
		scanf_s("%d", &p->data);
		if (p->data == 0) {
			return head;
		}
		//在迭代插入新的节点的过程中一直使P指向新的节点，q指向当前节点
		p->next = NULL;
		q->next = p;
		q = p;
	}
}

void showList(Node *m) {
	Node *p;
	p = m->next;//让p指针指向第一个节点
	while (p!=NULL)
	{	
		//注意头指针的数据是不需要输出的
		printf("%d\n", p->data);
		p = p->next;
	}
}
void DeleteListItem(Node *n,int x) {
	Node *p,*q,*pre; //p为循环指针，q指向需要删除的指针, pre始终为当前指针的前一位，类似双链表
	p = n->next;//让p指向第一个节点，跳过头节点
	pre = n;
	while (p!=NULL)
	{
		if (p->data==x)
		{	
			printf("找到要删除的数据%d---%d\n",p->data,x);
			q = p;//q指针指向需要删除的指针
			p = p->next;//循环指针跳到下一个位置
			pre->next = p;//此时，可以理解为前驱节点跳过要删除的点，next指向P
			free(q);//释放内存
			count--;
		}else
		{
			pre = p;
			p = p->next;
		}
	}
}

int main() {
	//创建好了一个链表
	Node *m = InitList();
	//输出链表中的数据信息
	showList(m);
	printf("请输入需要删除的元素: ");
	int d;
	scanf_s("%d", &d);
	//删除链表中指定元素
	DeleteListItem(m, d);
	//删除完再输出数据
	printf("删除了指定元素后的列表:\n", d);
	printf("链表总长度为:%d\n", count);
	showList(m);
	system("pause");
	return 0;
}

采用C语言实现：完整删除链表中指定位置的元素的代码。

原链表：3->4->5。现在要删除位置为2处的元素。

删除后的链表：3->5。
#include <stdio.h>
#include <stdlib.h>
#include <MacTypes.h>

/*定义节点*/
typedef struct Node {
    int data;
    struct Node *next;
} LinkedList;

/*使用头插法来构建一个链表*/
void push(struct Node **head_ref, int new_data);

/*给一个指针的指针作为引用，作为这个链表的头指针,进行删除指定位置的节点*/
void deleteNode(struct Node **head_ref, int position);

/*打印链表*/
void printList(LinkedList *node);

int main() {
    LinkedList *head_ref = NULL;
    //注意这里要传取地址符
    push(&head_ref, 3);
    push(&head_ref, 4);
    push(&head_ref, 5);
    deleteNode(&head_ref,2);
    printList(head_ref);
    return 0;
}

/*
 * 头插法的几步
 * 1.定义一个新的指针，给指针申请空间，使其变成一个新的节点。
 * 2.给这个新的节点data数据域赋值。
 * 3.将这个新的节点的next指针指向原来的开始节点（原头指针指向的节点）
 * 4.将原头指针左移移动到新的节点
 */
void push(struct Node **head_ref, int new_data) {

    LinkedList *new_node = (LinkedList *) malloc(sizeof(LinkedList));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

/*从给定节点往后打印链表*/
void printList(LinkedList *node) {
    //节点不为空，循环
    while (node != NULL) {
        //打印节点值
        printf(" %d \n", node->data);
        //指针后移
        node = node->next;
    }
}

/*删除指定位置的的节点*/
void deleteNode(struct Node **head_ref, int position) {

    //1.首先判断这个链表是否为空
    if (*head_ref == NULL) {
        return;
    }

    //2.创建一个指针存储头节点
    struct Node *temp = *head_ref;

    //3.如果这个position是0，那么直接移除掉头节点
    if (position == 0) {
        *head_ref = temp->next;
        free(temp);
        return;
    }

    //4.从头节点遍历，找到删除位置position的前驱节点,temp指向前驱
    for (int i = 0; temp != NULL && i < position - 1; ++i) {
        temp = temp->next;
    }

    //5.如果这个位置比链表还长
    if (temp == NULL || temp ->next == NULL){
        return;
    }

    //6.创建一个新的指针指向将要删除的节点的下一个节点
    //temp是删除节点的前驱
    //temp->next 这个节点是即将被删除的节点
    struct Node *next = temp->next->next;
    //7.删除节点
    free(temp->next);

    //8.将next节点连接在前驱节点temp后面
    temp->next=next;

}

输出：
 5 
 4 

删除链表中等于给定值 val 的所有节点。
题目源于领扣：https://leetcode-cn.com/problems/remove-linked-list-elements/description/

输入: 1->2->6->3->4->5->6, val = 6

输出: 1->2->3->4->5
分析：

当链表为空时，返回NULL
当链表不为空时

1.当前被删除节点是头节点（包含只有一个节点的情况）

2.被删除节点不是头节点

删除元素过程（以C++代码为例）

如图：



注意：

当删除的节点就是头结点时，新的头结点（即cur->next）就是NULL，满足删除指定val的所有元素的条件。
当判断完结点是否为头结点时，不能漏掉cur=cur->next这一句，因为指定val值的元素不止一个，所以在删除一个结点之后，还要让cur继续向后走，继续排查。
下面的C++代码和C语言代码有一点点细微的差别，C语言中有一句free(cur)，但C++代码中没有，需要注意是，C语言中的链表结点是一个结构体，是由malloc开辟出来的空间，所以使用free来释放这段内存空间，是真正意义的将结点删除。而在C++代码中，涉及到类和对象，使用free释放内存仅仅释放了对象的内存，而没有调用析构函数，正确的删除对象需要delete，所以这里C++代码中不用free，删除节点实质上是将目标结点覆盖。

完整代码：

C++:
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* cur = head;
        ListNode* prev = NULL;
        
        //当链表为空
        if(head==NULL)
        {
            return head;
        }
        
        //当链表不为空
        while(cur)
        {
            if(cur->val == val)
            {
                //当前节点是头节点，那么prev==NULL
                if(prev == NULL)
                {
                    head=cur->next;
                }
                else{
                    prev->next=cur->next;
                }
                
                cur=cur->next;
            }
            else
            {
                prev=cur;
                cur=cur->next;
            }
           
        }
        return head;
    }
};

C:
/**
- Definition for singly-linked list.
- struct ListNode {
- int val;
- struct ListNode *next;
- };
  */
struct ListNode* removeElements(struct ListNode* head, int val) {
      struct ListNode* cur=head;
        struct ListNode* prev=NULL;
        
        while(cur)
        {
            if(cur->val==val)
            {
               struct ListNode* next=cur->next;
               if(prev==NULL)
               {
                    head=cur->next;
               }
               else
               {
                   prev->next=cur->next;
                }
            
              free(cur);
              cur = next;
            }
             else
           {
             prev=cur;
             cur=cur->next;
             }
       }
   
      return head;
}