数据结构与算法(一) 链表（代码示例）

不念不忘少年蓝@ 2022-09-05 12:50 210阅读 0赞

### 数据结构与算法 ###

*   *  1. 什么是单链表
     *  2. 实现单链表的增删操作
     *   *  1. 插入单链表第i个结点，即插入到ai-1与ai之间的具体步骤：
         *  2. 删除第i个结点
     *  3. 删除链表的重复数据
     *  4. 找出单链表中的倒数第k个元素
     *  5. 实现链表的反转
     *  6. 从尾到头输出单链表
     *  7. 查找单链表的中间结点
     *  8. 检测一个链表是否有环
     *  9. 在不知道头指针的情况下删除指定结点
     *  10. 判断两个链表是否相交
     *  11. 总结

## 1. 什么是单链表 ##

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

## 2. 实现单链表的增删操作 ##

### 1. 插入单链表第i个结点，即插入到ai-1与ai之间的具体步骤： ###

1.  找到 ai-1 的引用 p
2.  生成一个数据域为 x 的新结点 s
3.  设置p.next = s
4.  设置s.next = ai

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzUyMDY3MA_size_16_color_FFFFFF_t_70]

### 2. 删除第i个结点 ###

1.  找到ai-1的存储位置p
2.  p.next指向ai的直接后继结点ai+1

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzUyMDY3MA_size_16_color_FFFFFF_t_70 1]  
代码示例：

/** * 描述： Java对链表的一些操作 * * @author Ye * @version 1.0 * @date 2021/8/17 17:06 */
    public class MyLinkedList { 
        /** * 链表头的引用 * */
        Node head = null;
    
        /** * 向链表中插入数据 * @param data: 插入数据的内容 * */
        public void addNode(int data){ 
            Node newNode = new Node(data);
            if (head == null){ 
                head = newNode;
                return;
            }
            Node temp = head;
            while (temp.next != null){ 
                temp = temp.next;
            }
            temp.next = newNode;
        }
    
        /** * @param index: 删除第index个结点 * @return 成功返回true，失败返回false * */
        public Boolean deleteNode(int index){ 
            if (index < 1 || index > length()){ 
                return false;
            }
            if (index == 1){ 
                head = head.next;
                return true;
            }
            int i = 2;
            Node preNode = head;
            Node curNode = preNode.next;
            while (curNode != null){ 
                if (i == index){ 
                    preNode.next = curNode.next;
                    return true;
                }
                preNode = curNode;
                curNode = curNode.next;
                i++;
            }
            return true;
        }
    
        /** * @return 返回结点的长度 * */
        public int length(){ 
            int length = 0;
            Node temp = head;
            while (temp != null){ 
                length ++;
                temp = temp.next;
            }
            return length;
        }
    
        /** * 对链表进行排序 * 返回排序后的头结点 * */
        public Node orderList(){ 
            Node nextNode = null;
            int temp = 0;
            Node curNode = head;
            while (curNode != null){ 
                nextNode = curNode.next;
                while (nextNode != null){ 
                    if (curNode.data > nextNode.data){ 
                        temp = curNode.data;
                        curNode.data = nextNode.data;
                        nextNode.data = temp;
                    }
                    nextNode = nextNode.next;
                }
                curNode = curNode.next;
            }
            return head;
        }
    
    
        public void printList(){ 
            Node temp = head;
            while (temp != null){ 
                System.out.print(temp.data + " ");
                temp = temp.next;
            }
            System.out.println();
        }
    
        public static void main(String[] args) { 
            MyLinkedList list = new MyLinkedList();
            list.addNode(95);
            list.addNode(56);
            list.addNode(84);
            list.addNode(44);
            list.addNode(67);
            list.addNode(45);
            list.addNode(58);
            list.addNode(94);
            list.addNode(14);
            list.addNode(7);
            System.out.println("链表长度为： " + list.length());
            System.out.print("排序前： ");
            list.printList();
            list.orderList();
            System.out.print("排序后： ");
            list.printList();
            System.out.println("删除第三个结点后：");
            list.deleteNode(3);
            list.printList();
        }
    }
    
    /** * 结点类 * * */
    class Node{ 
        Node next = null;
        int data;
        public Node(int data){ 
            this.data = data;
        }
    }

运行截图：  
![在这里插入图片描述][8eae7dd42af14cb9beabd43ddb5e5a07.png]

## 3. 删除链表的重复数据 ##

从链表中删除重复数据，可以遍历链表，把遍历到的值存储到一个hashtable，在遍历过程中，若当前访问的值在hashtable中已经存在，则说明这个数据是重复的，因此可以删除。  
代码如下：

/** * 删除单链表的重复数据 * @param head:单链表的头指针 * */
        public void deleteDuplecate(Node head){ 
            Hashtable<Integer,Integer> table = new Hashtable<>();
            Node temp = head;
            Node pre = null;
            while (temp != null){ 
                if (table.containsKey(temp.data)){ 
                    pre.next = temp.next;
                }else { 
                    table.put(temp.data,1);
                    pre = temp;
                }
                temp = temp.next;
            }
        }

第二种方法是对链表双重循环遍历  
代码如下：

/** * 删除单链表的重复数据 * @param head:单链表的头指针 * */
        public void deleteDuplecate(Node head){ 
            Node p = head;
            while (p != null){ 
                Node q = p;
                while (q.next != null){ 
                    if (p.data == q.data){ 
                        q.next = q.next.next;
                    }else { 
                        q = q.next;
                    }
                    p = p.next;
                }
            }
        }

## 4. 找出单链表中的倒数第k个元素 ##

为了找出单链表中的倒数第k个元素，最容易想到的方法是首先遍历一遍单链表，求出整个单链表的长度 n，然后将倒数第k 个，转换为正数第 n -k 个，接下去遍历一次就可以得到结果。但是该方法存在一个问题，即需要对链表进行两次遍历，第一次遍历用于求解单链表的长度，第二次遍历用于查找正数第 n-k个元素。

存在一种更高效的方式，只需要一次遍历即可查找到倒数第k个元素。由于单链表只能从头到尾依次访问链表的各个结点，因此，如果要找出链表的倒数第k个元素的话，也只能从头到尾进行遍历查找，在查找过程中，设置两个指针，让其中一个指针比另一个指针（虽然 Java 语言没有指针的概念，但是引用与指针有着非常相似的性质。为了便于理解，在后续的介绍中都采用指针的概念来介绍）先前移k-1 步，然后两个指针同时往前移动。循环直到先行的指针值为 NULL 时，另一个指针所指的位置就是所要找的位置。  
程序代码如下：

/** * 找出单链表中的倒数第k个元素 * @param head:单链表的头指针 * @param k:倒数第k个元素 * */
        public Node findElem(Node head,int k){ 
            if (k < 1){ 
                return null;
            }
            Node p1 = head;
            Node p2 = head;
            for (int i=0;i<k-1&&p1 != null;i++){ 
                p1 = p1.next;
            }
            if (p1 == null){ 
                System.out.println(" k不合法 ");
                return null;
            }
            while (p1.next != null){ 
                p1 = p1.next;
                p2 = p2.next;
            }
            return p2;
        }

## 5. 实现链表的反转 ##

为了正确地反转一个链表，需要调整指针的指向，而与指针操作相关代码总是非常容易出错的。先举个例子看一下具体的反转过程，例如，i，m，n 是 3 个相邻的结点，假设经过若干步操作，已经把结点 i之前的指针调整完毕，这些结点的 next 指针都指向前面一个结点。现在遍历到结点m，当然，需要调整结点的 mext 指针，让它指向结点 i，但需要注意的是，一旦调整了指针的指向，链表就断开了，因为已经没有指针指向结点 n，没有办法再遍历到结点n了，所以为了避免链表断开，需要在调整 m 的 next 之前要把 n 保存下来。接下来试着找到反转后链表的头结点，不难分析出反转后链表的头结点是原始链表的尾结点，即 next 为空指钟的结点。  
下面给出非递归方法实现链表的反转的实现代码。

/** * 实现链表反转 * @param head:单链表的头指针 * */
        public void ReverseIteratively(Node head){ 
            Node pReversedHead = head;
            Node pNode = head;
            Node pPrev = null;
            while (pNode != null){ 
                Node pNext = pNode.next;
                if (pNext == null){ 
                    pReversedHead = pNode;
                }
                pNode.next = pPrev;
                pPrev = pNode;
                pNode = pNext;
            }
            this.head = pReversedHead;
        }

## 6. 从尾到头输出单链表 ##

可以改变链表的方向实现从尾到头输出单链表，但是比较麻烦；我们可以这样想，把链表的数据一个一个按顺序放到栈中，到最后一个的时候，取出来，因为栈的先进后出的结构，可以从尾到头输出；具体可以用递归去实现，因为递归就是栈结构：  
代码如下：

/** * 从尾到头输出单链表 * @param pListHead:单链表的头指针 * */
        public void printListReversely(Node pListHead){ 
            if (pListHead != null){ 
                printListReversely(pListHead.next);
                System.out.print(pListHead.data + " ");
            }
        }

## 7. 查找单链表的中间结点 ##

可以先遍历一遍求出长度，然后在遍历 length/2 找出长度，但是这样就遍历两遍了；还有一种更高效的办法就是，定义两个指针，一个一次走一步，一个一次走两步，当走两步的指针到达链表结尾的时候，就是慢指针走到中间的时候。  
代码如下：

/** * 寻找单链表的中间结点 * @param head:单链表的头指针 * */
        public Node searchMid(Node head){ 
            Node p = this.head;
            Node q = this.head;
            while (p != null && p.next != null && p.next.next != null){ 
                p = p.next.next;
                q = q.next;
            }
            return q;
        }

## 8. 检测一个链表是否有环 ##

定义两个指针，一个一次走一步，一个一次走两步，当走两步的指针到达尾部时，说明是单链表；否则，当走两步的指针和走一步的指针指向同一个结点的时候，就证明是有环链表。  
代码如下：

/** * 检测一个链表是否有环 * @param head:单链表的头指针 * */
        public boolean isLoop(Node head){ 
            Node fast = head;
            Node slow = head;
            if (fast == null){ 
                return false;
            }
            while (fast != null && fast.next != null){ 
                fast = fast.next.next;
                slow = slow.next;
                if (fast == slow){ 
                    return true;
                }
            }
            return !(fast == null || fast.next == null);
        }

## 9. 在不知道头指针的情况下删除指定结点 ##

可以分情况讨论：

1.  若待删除的结点为链表尾结点，则无法删除，因为删除后无法使其前驱结点的 next 指针为空。
2.  若待删除的结点不是尾结点，则可以通过交换这个结点与其后继结点的值，然后删除后继结点。

代码实现如下：

/** * 在不知道头指针的情况下删除指定结点 * @param n:要删除的结点 * */
        public boolean deleteNode(Node n){ 
            if (n == null || n.next == null){ 
                return false;
            }
            int temp = n.data;
            n.data = n.next.data;
            n.next.data = temp;
            n.next = n.next.next;
            return true;
        }

## 10. 判断两个链表是否相交 ##

对于单链表来说，如果两个链表相交那么他们的尾结点一定相同，可以用这个实现判断逻辑  
代码如下：

/** * 判断两个链表是否相交 * @param h1:链表头指针 * @param h2:链表头指针 * */
        public static boolean isIntersect(Node h1,Node h2){ 
            if (h1 == null || h2 == null){ 
                return false;
            }
            Node tail1 = h1;
            // 找到链表h1的最后一个结点
            while (tail1.next != null){ 
                tail1 = tail1.next;
            }
            Node tail2 = h2;
            // 找到链表h1的最后一个结点
            while (tail2.next != null){ 
                tail2 = tail2.next;
            }
            return tail1 == tail2;
        }

如果两个链表相交，如何找到它们相交的第一个结点？

首先分别计算两个链表 head1、head2 的长度 lenl 和len2（假设 lenl >len2），接着先对链表head1 遍历（lenl -len2）个结点到结点 p，此时结点p 与 head2 到它们相交的结点的距离相同，此时同时遍历两个链表，直到遇到相同的结点为止，这个结点就是它们相交的结点。需要注意的是，在查找相交的第一个结点前，需要先判断两个链表是否相交，只有在相交的情况下才有必要去找它们的交点，否则根本就没有必要了。

代码如下：

/** * 判断两个链表是否相交,并返回相交的第一个结点 * @param h1:链表头指针 * @param h2:链表头指针 * */
        public static Node getFirstMeetNode(Node h1,Node h2){ 
            if (h1 == null || h2 == null){ 
                return null;
            }
            Node tail1 = h1;
            int len1 = 1;
            //找到链表h1的最后一个结点
            while (tail1.next != null){ 
                tail1 = tail1.next;
                len1++;
            }
            Node tail2 = h2;
            int len2 = 1;
            //找到链表h2的最后一个结点
            while (tail2.next != null){ 
                tail2 = tail2.next;
                len2++;
            }
            //两链表不相交
            if (tail1 != tail2){ 
                return null;
            }
            Node t1 = h1;
            Node t2 = h2;
            //找出较长的链表,先遍历
            if (len1 > len2){ 
                int d = len1 - len2;
                while (d != 0){ 
                    t1 = t1.next;
                    d--;
                }
            }else { 
                int d = len2 - len1;
                while (d != 0){ 
                    t2 = t2.next;
                    d--;
                }
            }
            while (t1 != t2){ 
                t1 = t1.next;
                t2 = t2.next;
            }
            return t1;
        }

## 11. 总结 ##

完整代码如下：

package com.example.demo;
    
    import java.util.Hashtable;
    
    /** * 描述： Java对链表的一些操作 * * @author Ye * @version 1.0 * @date 2021/8/17 17:06 */
    public class MyLinkedList { 
        /** * 链表头的引用 * */
        Node head = null;
    
        /** * 向链表中插入数据 * @param data: 插入数据的内容 * */
        public void addNode(int data){ 
            Node newNode = new Node(data);
            if (head == null){ 
                head = newNode;
                return;
            }
            Node temp = head;
            while (temp.next != null){ 
                temp = temp.next;
            }
            temp.next = newNode;
        }
    
        /** * @param index: 删除第index个结点 * @return 成功返回true，失败返回false * */
        public Boolean deleteNode(int index){ 
            if (index < 1 || index > length()){ 
                return false;
            }
            if (index == 1){ 
                head = head.next;
                return true;
            }
            int i = 2;
            Node preNode = head;
            Node curNode = preNode.next;
            while (curNode != null){ 
                if (i == index){ 
                    preNode.next = curNode.next;
                    return true;
                }
                preNode = curNode;
                curNode = curNode.next;
                i++;
            }
            return true;
        }
    
        /** * @return 返回结点的长度 * */
        public int length(){ 
            int length = 0;
            Node temp = head;
            while (temp != null){ 
                length ++;
                temp = temp.next;
            }
            return length;
        }
    
        /** * 对链表进行排序 * 返回排序后的头结点 * */
        public Node orderList(){ 
            Node nextNode = null;
            int temp = 0;
            Node curNode = head;
            while (curNode != null){ 
                nextNode = curNode.next;
                while (nextNode != null){ 
                    if (curNode.data > nextNode.data){ 
                        temp = curNode.data;
                        curNode.data = nextNode.data;
                        nextNode.data = temp;
                    }
                    nextNode = nextNode.next;
                }
                curNode = curNode.next;
            }
            return head;
        }
    
        /** * 删除单链表的重复数据 * @param head:单链表的头指针 * */
        public void deleteDuplecate(Node head){ 
            Hashtable<Integer,Integer> table = new Hashtable<>();
            Node temp = head;
            Node pre = null;
            while (temp != null){ 
                if (table.containsKey(temp.data)){ 
                    pre.next = temp.next;
                }else { 
                    table.put(temp.data,1);
                    pre = temp;
                }
                temp = temp.next;
            }
        }
    
    // /**
    // * 删除单链表的重复数据
    // * @param head:单链表的头指针
    // * */
    // public void deleteDuplecate(Node head){ 
    // Node p = head;
    // while (p != null){ 
    // Node q = p;
    // while (q.next != null){ 
    // if (p.data == q.data){ 
    // q.next = q.next.next;
    // }else { 
    // q = q.next;
    // }
    // p = p.next;
    // }
    // }
    // }
    
        /** * 找出单链表中的倒数第k个元素 * @param head:单链表的头指针 * @param k:倒数第k个元素 * */
        public Node findElem(Node head,int k){ 
            if (k < 1){ 
                return null;
            }
            Node p1 = head;
            Node p2 = head;
            for (int i=0;i<k-1&&p1 != null;i++){ 
                p1 = p1.next;
            }
            if (p1 == null){ 
                System.out.println(" k不合法 ");
                return null;
            }
            while (p1.next != null){ 
                p1 = p1.next;
                p2 = p2.next;
            }
            return p2;
        }
    
    
        /** * 实现链表反转 * @param head:单链表的头指针 * */
        public void reverseIteratively(Node head){ 
            Node pReversedHead = head;
            Node pNode = head;
            Node pPrev = null;
            while (pNode != null){ 
                Node pNext = pNode.next;
                if (pNext == null){ 
                    pReversedHead = pNode;
                }
                pNode.next = pPrev;
                pPrev = pNode;
                pNode = pNext;
            }
            this.head = pReversedHead;
        }
    
        /** * 从尾到头输出单链表 * @param pListHead:单链表的头指针 * */
        public void printListReversely(Node pListHead){ 
            if (pListHead != null){ 
                printListReversely(pListHead.next);
                System.out.print(pListHead.data + " ");
            }
        }
    
        /** * 寻找单链表的中间结点 * @param head:单链表的头指针 * */
        public Node searchMid(Node head){ 
            Node p = this.head;
            Node q = this.head;
            while (p != null && p.next != null && p.next.next != null){ 
                p = p.next.next;
                q = q.next;
            }
            return q;
        }
    
        /** * 检测一个链表是否有环 * @param head:单链表的头指针 * */
        public boolean isLoop(Node head){ 
            Node fast = head;
            Node slow = head;
            if (fast == null){ 
                return false;
            }
            while (fast != null && fast.next != null){ 
                fast = fast.next.next;
                slow = slow.next;
                if (fast == slow){ 
                    return true;
                }
            }
            return !(fast == null || fast.next == null);
        }
    
        /** * 检测一个链表是否有环, 并找到环入口点 * @param head:单链表的头指针 * */
        public Node findLoopPort(Node head){ 
            Node slow = head;
            Node fast = head;
            while (fast != null && fast.next != null){ 
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast){ 
                    break;
                }
            }
            if (fast == null || fast.next == null){ 
                return null;
            }
            slow = head;
            while (slow != fast){ 
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    
        /** * 在不知道头指针的情况下删除指定结点 * @param n:要删除的结点 * */
        public boolean deleteNode(Node n){ 
            if (n == null || n.next == null){ 
                return false;
            }
            int temp = n.data;
            n.data = n.next.data;
            n.next.data = temp;
            n.next = n.next.next;
            return true;
        }
    
        /** * 判断两个链表是否相交 * @param h1:链表头指针 * @param h2:链表头指针 * */
        public static boolean isIntersect(Node h1,Node h2){ 
            if (h1 == null || h2 == null){ 
                return false;
            }
            Node tail1 = h1;
            // 找到链表h1的最后一个结点
            while (tail1.next != null){ 
                tail1 = tail1.next;
            }
            Node tail2 = h2;
            // 找到链表h1的最后一个结点
            while (tail2.next != null){ 
                tail2 = tail2.next;
            }
            return tail1 == tail2;
        }
    
    
        /** * 判断两个链表是否相交,并返回相交的第一个结点 * @param h1:链表头指针 * @param h2:链表头指针 * */
        public static Node getFirstMeetNode(Node h1,Node h2){ 
            if (h1 == null || h2 == null){ 
                return null;
            }
            Node tail1 = h1;
            int len1 = 1;
            //找到链表h1的最后一个结点
            while (tail1.next != null){ 
                tail1 = tail1.next;
                len1++;
            }
            Node tail2 = h2;
            int len2 = 1;
            //找到链表h2的最后一个结点
            while (tail2.next != null){ 
                tail2 = tail2.next;
                len2++;
            }
            //两链表不相交
            if (tail1 != tail2){ 
                return null;
            }
            Node t1 = h1;
            Node t2 = h2;
            //找出较长的链表,先遍历
            if (len1 > len2){ 
                int d = len1 - len2;
                while (d != 0){ 
                    t1 = t1.next;
                    d--;
                }
            }else { 
                int d = len2 - len1;
                while (d != 0){ 
                    t2 = t2.next;
                    d--;
                }
            }
            while (t1 != t2){ 
                t1 = t1.next;
                t2 = t2.next;
            }
            return t1;
        }
    
        public void printList(){ 
            Node temp = head;
            while (temp != null){ 
                System.out.print(temp.data + " ");
                temp = temp.next;
            }
            System.out.println();
        }
    
        public static void main(String[] args) { 
            MyLinkedList list = new MyLinkedList();
            MyLinkedList list1 = new MyLinkedList();
            list1.addNode(61);
            list1.addNode(29);
    
            list.addNode(95);
            list.addNode(56);
            list.addNode(7);
            list.addNode(44);
            list.addNode(67);
            list.addNode(45);
            list.addNode(58);
            list.addNode(94);
            list.addNode(7);
            list.addNode(7);
            list1.head.next.next = list.head.next.next.next.next;
            System.out.println("链表长度为： " + list.length());
            System.out.print("排序前： ");
            list.printList();
            list.orderList();
            System.out.print("排序后： ");
            list.printList();
            System.out.println("删除第三个结点后：");
            list.deleteNode(3);
            list.printList();
            System.out.println("删除重复数据后：");
            list.deleteDuplecate(list.head);
            list.printList();
            System.out.println("倒数第三个数：");
            System.out.println(list.findElem(list.head,3).data);
            list.reverseIteratively(list.head);
            System.out.println("链表反转后：");
            list.printList();
            System.out.println("从尾输出单链表：");
            list.printListReversely(list.head);
            System.out.println();
            System.out.println("单链表的中间结点：");
            System.out.println(list.searchMid(list.head).data);
            System.out.println("判断是不是循环链表：");
            System.out.println(list.isLoop(list.head));
            System.out.println("删除倒数第三个结点：");
            System.out.println(list.deleteNode(list.findElem(list.head,3)));
            System.out.println("判断两个链表是否相交：");
            System.out.println(isIntersect(list1.head,list.head));
            System.out.println("找出链表相交的第一个结点：");
            System.out.println(getFirstMeetNode(list1.head,list.head).data);
        }
    }
    
    /** * 结点类 * */
    class Node{ 
        Node next = null;
        int data;
        public Node(int data){ 
            this.data = data;
        }
    }

测试截图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzUyMDY3MA_size_16_color_FFFFFF_t_70 2]

参考：《Java程序员面试笔试宝典》 何昊、薛鹏、叶向阳 编著

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzUyMDY3MA_size_16_color_FFFFFF_t_70]: /images/20220829/655179acc6d84d8292684dab3f9ec702.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzUyMDY3MA_size_16_color_FFFFFF_t_70 1]: /images/20220829/6e371ef3af7c436f939dc57b34619582.png
[8eae7dd42af14cb9beabd43ddb5e5a07.png]: /images/20220829/ab16221eaa5e43118d8abb83f64f7ad5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzUyMDY3MA_size_16_color_FFFFFF_t_70 2]: /images/20220829/f1c7ee3357f049aba11c6ba55628b110.png