递归删除链表中值为X的结点_用递归方法删除单链表中值为x的结点

递归删除链表中值为X的结点

在递归方法中传入,当前结点,和它的前驱结点pre,如果当前结点cur的值data为x,则删除当前结点,pre->next=cur->next,不然继续向下递归

实现代码

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


typedef int Elemtype;

//单链表

typedef struct LNode
{
    Elemtype data;//存放数据
    struct LNode *next; //指向LNode的一个指针

} LNode,*LinkList; //相当于取别名,LNode代表一个节点,LinkList代表整个单链表(指向LNode的一个指针)

void PrintList(LinkList L)
{
    LinkList p;
    p=L->next;//找到头指针指向节点,开始遍历
    printf("链表元素如下：\n");
    while(p!=NULL)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
}


//尾插法
LinkList List_TailInsert(LinkList L)
{
    int x;
    L=(LinkList)malloc(sizeof(LNode));
    LNode *r=L,*s;
    scanf("%d",&x);

    while(x!=9999)
    {
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        r=s;
        scanf("%d",&x);
    }
    r->next=NULL;
    return L;
}


void Del_X(LNode *pre,LNode *cur,Elemtype x)
{
    if(cur==NULL) return ;//递归到链表结束

    if(cur->data==x)
    {
        pre->next=cur->next;
        free(cur);//删除当前结点
        Del_X(pre,pre->next,x);
    }else{

        Del_X(cur,cur->next,x);//如果当前节点不为x,则向下递归
    }

}
int main()
{

    LinkList L;//使用头插法 这里的L1就是一个头指针
    printf("请输入链表元素,输入9999表示结束\n");
    L=List_TailInsert(L); // 1 2 3 4
    PrintList(L);
    printf("请输入x的值:");
    int x;
    scanf("%d",&x);
    printf("\n");
    printf("递归删除值为x的结点\n");
    Del_X(L,L->next,x);
    PrintList(L);
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84