猿创征文 |『牛客|每日一题』循环链表

👨‍🎓作者简介：一位喜欢写作，计科专业大三菜鸟

🏡个人主页：starry陆离

🕒首发日期：2022年8月29日星期一

🍁每日推荐：牛客网-面试神器

1.每日一题

描述
请你实现一个链表。
操作：
insert x y：将y加入链表，插入在第一个值为x的结点之前。若链表中不存在值为x的结点，则插入在链表末尾。保证x，y为int型整数。
delete x：删除链表中第一个值为x的结点。若不存在值为x的结点，则不删除。
输入描述：
第一行输入一个整数n (1 < n < 10⁴ )，表示操作次数。
接下来的n行，每行一个字符串，表示一个操作。保证操作是题目描述中的一种。
输出描述：
输出一行，将链表中所有结点的值按顺序输出。若链表为空，输出"NULL"(不含引号)。

2.测试案例

5
insert 0 1
insert 0 3
insert 1 2
insert 3 4
delete 4
1
2
3
4
5
6

2 1 3
1

3.思路分析

这题是要我们自己实现一个链表。链表是一种物理结构上非连续、非顺序的存储结构。而链表中常用的就是增删改查。

3.1增

将y值插入到x节点之前

1. 找到节点x的前一个节点xp，
2. 让节点y指向节点x，也就是y.next=xp.next
3. 最后让节点xp指向节点y，也就是xp.next=y

3.2删

删除节点x

1. 找到节点x的前一个节点xp，
2. 让xp指向x的下一个节点，即xp.next=xp.next.next

4.代码实现

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sca=new Scanner(System.in);
        MyList list=new MyList();
        int n=sca.nextInt();
        sca.nextLine();
        String[] s;
        String op;
        int x,y;
        for(int i=0;i<n;++i){
            s=sca.nextLine().split(" ");
            op=s[0];
            x=Integer.parseInt(s[1]);
            if(op.equals("insert")){
                y=Integer.parseInt(s[2]);
                list.insert(x,y);
            }else{
                list.delete(x);
            }
        }
        System.out.println(list);
    }
}
//定义节点
class Node{
    int val;//值
    Node next;//指向下一个节点
    public Node(int val){
        this.val=val;
    }
}
//自定义链表
class MyList{
    Node root;//头节点
    public MyList(){
        root =new Node(-1);
    }
    
    //查找值为x的节点的前一个节点
    public Node findPre(int x){
        Node cur=root;
        while(cur.next!=null&&cur.next.val!=x){
            cur=cur.next;
        }
        return cur;
    }
    
    //将y值插入到x节点之前
    public void insert(int x,int y){
        Node xPre=findPre(x);//查找值为x的节点的前一个节点
        Node yNode=new Node(y);//创建y节点
        yNode.next=xPre.next;//节点y的下一个节点是x节点指向的下一个节点
        xPre.next=yNode;//更新x节点的下一个节点是y节点
    }
    
    //删除节点x
    public void delete(int x){
        Node xPre=findPre(x);//查找值为x的节点的前一个节点
        if(xPre.next!=null){
            xPre.next=xPre.next.next;
        }
    }
    
    //输出链表中的值
    public String toString(){
        StringBuffer sb=new StringBuffer();
        if(root.next==null){
            return "NULL";
        }else{
            Node cur=root.next;
            while(cur!=null){
                sb.append(cur.val+" ");
                cur=cur.next;
            }
        }
        return sb.toString();
    }
}
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

5.每日推荐

📚订阅专栏：『牛客刷题集锦』

🍁每日推荐：基础算法无论在研究生面试还是求职面试都是十分重要的一环，这里推荐一款算法面试神器：牛客网-面试神器；算法题只有多刷勤刷才能保持思路与手感，大家赶紧行动起来吧（温馨提示：常见的面试问答题库也很nice哦）

如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦