试图编写一个链表，实现插入后，试着编写一下删除操作。（这种使用数组的方式可能会浪费内存，但是请暂时忽略这点）
作为练习的判断，请输出删除链表内所有元素x后的序列。数组保证删除后仍不为空。
题目来源：
https://www.dotcpp.com/oj/problem2024.html
输入
第一行包括一个数字n(n<100000)，表示链表内元素的个数。
接下来一行，共n个整数，表示链表内的数据
接下来一个数字x，表示要删除的元素。
输出
一行，表示删除后的序列。
样例输入
8
2 3 4 4 4 5 3 8
4
样例输出
2 3 5 3 8
这里主要讲解一下将所有重复的x元素删除的代码:
过程分析:
Number * delete(int num,Number *head){
Number *current,*pre;
current = head;
pre = NULL;
if(current == NULL){
printf("error");//空链表
exit(0);
}else{
while(current != NULL){
if(current->num == num){
//如果当前的节点是要删除的节点，那么就判断删除的节点是否为头结点
if(pre == NULL){
//如果删除的节点是头结点，那么原来链表的第二个节点就是头节点，此时pre依旧是NULL
head = current->next;
}else{
//删除的节点不是头结点，那么pre的下一个节点就是当前节点的下一个节点
pre->next = current->next;
}
}else pre = current; //这一步需要注意的，不可以没有else，直接就写pre = current
current = current->next;
}
}
return head;
}
正确的完整
的代码:
#include<stdio.h>
#include<stdlib.h>
typedef struct NUMBER{
int num;
struct NUMBER *next;
}Number;
//创造链表
Number * create(int n){
Number *head,*current,*node;
int i;
head = NULL;
for(i = 1; i <= n; i++){
node = (Number *)malloc(sizeof(Number));
scanf("%d",&node->num);
node->next = NULL;
if(i == 1) head = node;
else current->next = node;
current = node;
}
return head;
}
Number * delete(int num,Number *head){
Number *current,*pre;
current = head;
pre = NULL;
if(current == NULL){
printf("error");//空链表
exit(0);
}else{
while(current != NULL){
if(current->num == num){
//如果当前的节点是要删除的节点，那么就判断删除的节点是否为头结点
if(pre == NULL){
//如果删除的节点是头结点，那么原来链表的第二个节点就是头节点，此时pre依旧是NULL
head = current->next;
}else{
//删除的节点不是头结点，那么pre的下一个节点就是当前节点的下一个节点
pre->next = current->next;
}
}else pre = current; //这一步需要注意的，不可以没有else，直接就写pre = current
current = current->next;
}
}
return head;
}
//遍历链表
void display(Number *head){
Number *current;
current = head;
if(current == NULL){
printf("error");//空链表的情况
exit(0);
}else{
while(current != NULL){
printf("%d ",current->num);
current = current->next;
}
printf("\n");
}
}
int main(){
int n,num;
Number *head;
scanf("%d",&n);//输入节点的个数
head = create(n);//创造n个节点的链表
scanf("%d",&num);//输入要删除的元素
head = delete(num,head);
display(head);
return 0;
}
运行结果:
类似的题目:
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1
输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]
来源：力扣（LeetCode）
链接：
https://leetcode-cn.com/problems/remove-linked-list-elements
对应的代码：
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode newHead = new ListNode(0);
newHead.next = head;
ListNode cur = newHead,pre = newHead;
while(cur != null){
/*
这一步必须放在这里，也正因如此，一开始的赋值为newHead,
因为如果在下面查找val的节点的时候，由于cur是null而退出循环的
时候，那么cur.next会发生报错，因此这一步需要放在找第一个不为val的
节点的代码前面
*/
cur = cur.next;
while(cur != null && cur.val == val) //找到第一个不等于val的节点
cur = cur.next;
pre.next = cur;
pre = pre.next;
}
return newHead.next;
}
}
运行结果:
看到这里，有小伙伴会问了，那我如果
在删除重复的x元素的代码中，将pre = current直接写，不需要else，会造成什么样的结果呢
？
Number * delete(int num,Number *head){
Number *current,*pre;
current = head;
pre = NULL;
if(current == NULL){
printf("error");//空链表
exit(0);
}else{
while(current != NULL){
if(current->num == num){
//如果当前的节点是要删除的节点，那么就判断删除的节点是否为头结点
if(pre == NULL){
//如果删除的节点是头结点，那么原来链表的第二个节点就是头节点，此时pre依旧是NULL
head = current->next;
}else{
//删除的节点不是头结点，那么pre的下一个节点就是当前节点的下一个节点
pre->next = current->next;
}
}
pre = current; //这一步没有else，直接就写pre = current
current = current->next;
}
}
return head;
}
请看过程分析:
从上面的分析中可以知道，如果没有else，即无论当前的节点是否为要删除的节点，都有进行pre = current的操作的话，那么就会导致没有将x删除全部，导致错误，不符合题目的要求了。
错误的
代码:
#include<stdio.h>
#include<stdlib.h>
typedef struct NUMBER{
int num;
struct NUMBER *next;
}Number;
Number * create(int n){
Number *head,*current,*node;
int i;
head = NULL;
for(i = 1; i <= n; i++){
node = (Number *)malloc(sizeof(Number));
scanf("%d",&node->num);
node->next = NULL;
if(i == 1) head = node;
else current->next = node;
current = node;
}
return head;
}
Number * delete(int num,Number *head){
Number *current,*pre;
current = head;
pre = NULL;
if(current == NULL){
printf("error");
exit(0);
}else{
while(current != NULL){
if(current->num == num){
//如果当前的节点是要删除的节点，那么就判断删除的节点是否为头结点
if(pre == NULL){
head = current->next;
}else{
pre->next = current->next;
}
}
pre = current;
current = current->next;
}
}
return head;
}
void display(Number *head){
Number *current;
current = head;
if(current == NULL){
printf("error");
exit(0);
}else{
while(current != NULL){
printf("%d ",current->num);
current = current->next;
}
printf("\n");
}
}
int main(){
int n,num;
Number *head;
scanf("%d",&n);
head = create(n);
scanf("%d",&num);
head = delete(num,head);
display(head);
return 0;
}
运行结果:
但是如果题目要求是删除所有的重复数字怎么办呢？这里插入一道算法题哈：
给定一个
排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现
的数字。
示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:
输入: 1->1->1->2->3
输出: 2->3
来源：力扣（LeetCode）
链接：
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/
通过观察题意，题目明确说明了，这个链表是已经排好序了的，那么这时候，我们要
判断当前这个节点是否已经重复，那么只需要判断这个节点的后一个节点的值和他是否相同就好了。然而真的是这样吗？如果这个节点是所有重复数字的最后一个数字呢？如果这个节点是最后一个节点的情况我们是否已经考虑过了呢？所以再上面思路的前提下，我们还需要考虑这些情况的，否则到时候就会发生意想不到的错误哦
。
解题思路：
准备工作：定义一个boolean类型的(这是再java中的)变量，表示这个节点前面是否已经出现过了flag,如果是在C语言中，则定义一个int类型的变量，如果为真，那么表明这个节点前面已经出现过和他重复的节点，否则这个节点的前面没有出现过和他重复的节点
1、通过定义一个假节点pre，使得这个假节点接在链表的头结点的前面。（即此时这个链表是一个带有假节点的链表了）,便于删除吧，
因为如果重复数字在头结点，那么如果没有这一步的话，那么操作相对会麻烦些，当然这是我的个人看法，如果有不同意见的，请多指教哈
！
2、同时
定义一个临时节点t，指向这个假节点pre
，因为后面我们需要让这个pre不断地后移，此时pre.next就不再是我们想要不重复数字链表的头结点了，所以需要定义临时节点t，指向pre，从而t.next就是我们最后得到链表的头结点
3、从左到右开始遍历链表，遍历链表的时候，我们需要注意的几种情况：
①如果当前节点是最后一个节点
②当前节点不是最后一个节点
这时候，这两种情况又分别包含了不同的情况：
①如果当前节点current是最后一个节点：
-
如果当前节点current是所有重复数字的最后一个节点，例如[1,2,3,3,4,4],那么我们只需要将pre.next = current.next即可
-
如果当前节点不是重复数字,例如[1,2,3,3,4,4,5]，那么我们就将pre.next = current即可
②如果当前节点不是最后一个节点： -
如果当前节点的值不等于这个节点的下一个节点的值，即current.val != current.next.val，此时我们需要注意了，此时当前节点可能使重复数字的最后一个节点，这时候我们需要通过上面定义的flag变量来判断当前节点的前面是否已经出现过了和他重复一样的节点，如果没有，那么就将进行pre.next = current； pre = current的操作，否则，如果有，那么让flag取反。
-
如果当前节点的值等于这个节点的下一个节点的值，那么我们就让上面定义的flag变量为真即可。
对应的代码(java实现的):
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null)
return head;//如果链表为空或者只有一个链表的时候，那么就返回这个节点
ListNode pre = new ListNode(0);
ListNode t = pre;//定义一个临时变量，指向pre这个节点的地址
pre.next = head;//定义一个带有假节点的链表，到最后只要返回pre.next即可
ListNode current = head;
boolean flag= false;//表示当前这个节点没有出现过
while(current != null){
if(current.next == null){
/*
如果当前这个节点是最后一个数那么需要分两种情况进行讨论
最后这个节点再前面已经出现过了，那么pre.next就直接为null
即可，否则如果最后一个节点没有出现过，那么直接将pre.next =
current即可
*/
if(flag == true)
pre.next = null;
else
pre.next = current;
break;
}
//如果这个节点不是最后一个节点
if(current.val != current.next.val){
if(!flag){
//如果当前这个节点前面没有出现过，那么就将pre接在这个节点的前面,之后将pre后移
pre.next = current;
pre = current;
}
flag = false;//这个是考虑到当前节点是最后一个重复的数字，如果没有这一步的话，那么就会导致flag一直为true，从而没有办法将不重复的数字进行拼接
}else{
flag = true;
}
current = current.next;
}
return t.next;//由于再遍历终pre是发生了移动的，所以不可以返回pre.next
}
}
有伙伴会问了，那如果题目
不是排好序
的，要求你将所有的重复数字删除怎么办呢？比如1，2，4，4，3，5，4，4，8，要求将所有的重复数字删除，并且
按照出现的先后顺序遍历
，最后得到1,2,4,3,5,8？那这样又该怎样做呢？
其实我的做法是这样的：
1、定义一条新链表，表示最后遍历的链表,也就是最后的结果
2、遍历原来的链表，
将当前节点的值在新链表中进行查找，判断新链表中是否含有这个节点的值，如果含有了，那么就不用做任何操作，直接后移到下一个节点，如果没有，那么就将当前节点的值插入到新链表的尾节点的地方
，从而实现新链表中没有重复数字，同时每一个数字是按照原来链表的先后顺序进行排列的。
3、重复上述操作，直到链表遍历为止。这时候，返回新链表的头节点即可。
对应的代码(C语言):
#include<stdio.h>
#include<stdlib.h>
typedef struct NODE{
int val;
struct NODE *next;
}Node;
typedef Node * LinkedList;
LinkedList create(){
int i,n;
LinkedList head,current,node;
/*
如果题目要求是排序的话，有假节点的操作会方便些
*/
head = (LinkedList)malloc(sizeof(Node));
head->next = NULL;//创建一个假节点，从而方便链表的增、删
current = head;
printf("请输入链表的个数:");
scanf("%d",&n);
for(i = 0; i < n; i++){
node = (LinkedList)malloc(sizeof(Node));
scanf("%d",&(node->val));
node->next = NULL;
current->next = node;
current = node;
}
return head;
}
void display(LinkedList head){
LinkedList current = head->next;
while(current != NULL){
if(current->next == NULL)//如果是最后一个节点，那么将它的值输出之后换行
printf("{%d}\n",current->val);
else
printf("{%d}->",current->val);
current = current->next;
}
}
LinkedList insertDestinct(LinkedList root,int val){
LinkedList current = root;
int flag = 0;//标记val是否已经在链表root中
while(current->next != NULL){
//如果当前节点的值不等于val，那么继续后移，判断是否含有val值得节点
//如果有，那么就不用将这个值插入到新链表中，否则插入
if(current->next->val == val){
flag = 1;
break;
}
current = current->next;
}
if(!flag){
//如果没有在root链表中没有找到val，那么将其插入
LinkedList node = (LinkedList)malloc(sizeof(Node));
node->val = val;
node->next = NULL;
/*
由于最后遍历结束得时候，current是最后一个节点，所以直接执行current->next = node
从而实现了新节点插入到链表尾部
*/
current->next = node;
}
return root;
}
LinkedList deleteRepeate(LinkedList head){
//遍历原来的链表
LinkedList current = head->next,root;
root = (LinkedList)malloc(sizeof(Node));
root->next = NULL;//新链表的假结点
while(current != NULL){
root = insertDestinct(root,current->val);
current = current->next;//
}
return root;
}
int main(){
LinkedList head;
head = create();
display(head);
printf("删除所有的重复数字，并按照原来顺序输出:");
head = deleteRepeate(head);
display(head);
return 0;
}
运行结果:
