算法通过村第一关——链表青铜挑战笔记

╰+哭是因爲堅強的太久メ 2024-03-17 20:41 71阅读 0赞

### 题目一：理解Java是如何构造出链表的 ###

> 单链表的内部结构

单链表中就像铁链一样，每个元素（节点）之间互相连接，包含多个节点，每个节点都有一个指向后继元素（节点）的next指针，最后一个元素的next指针指向null，如下图所示

![3ba50564771a4d8bb3f1ec5987f65e77.png][]

> Java单链表的构建过程

在Java中，单链表是由一个个Node节点连接起来的。Node节点是一个类，类中存放了数据属性（data）和下一个节点属性（Node），通常还会有对这两个属性的初始化的构造方法（主要是针对数据属性的初始化），当然，为了保证数据的安全性，会采用面向对象的封装性对属性使用private权限修饰，对外提供公有的get和set方法对这两个属性进行访问（如果只是测试，不考虑安全性的话，也可以将这两个属性设置为公有的，在外部直接对属性进行操作）。在构建好Node节点后，在为单链表插入元素时，一般是遍历操作，便可将元素数据赋值到Node节点的数据属性中，并将下一个元素对象赋值给Node节点的下一个节点属性。当遍历完所有元素后，所有的节点便形成了一个单链表。

> 节点代码构造

以下是节点的代码构造

public class Node {
        public  int data;
        public Node next;
    
        public Node(int data) {
            this.data = data;
        }
    }

> 单链表的构造代码

定义一个数组，将其元素转为单链表

public static void main(String[] args) {
            // 将一个数组转换为链表
            int [] arr = {4,17,6,20,22,35};
            SingleLinkedList linkedList = new SingleLinkedList();
            Node head = linkedList.transformSingleList(arr);
            linkedList.printSingleList(head);
        }

将数组转为单链表的方法

/**
         * 将数组转为链表
         * @param arr 数组
         * @return 链表头节点
         */
        public Node transformSingleList(int [] arr){
            Node head =new Node(arr[0]);
            // 使用辅助节点遍历将其余的元素 ，将其变为节点，添加在头节点之后，形成链表
            Node node = head;
            for (int i = 1 ; i < arr.length ;i ++) {
                Node temp = new Node(arr[i]);
                node.next = temp;
                node = temp;
            }
            return head;
        }

单链表遍历的方法

/**
         * 链表遍历
         * @param head  链表头节点
         */
        public void printSingleList(Node head){
            Node node = head;
            while (node != null){
                    System.out.print(node.data + "->");
                    node = node.next;
            }
        }

### 题目二：单链表的节点增加操作 ###

#### 问题 ####

> 链表增加节点，首部、中间和尾部分别会有什么问题，该如何处理？

#### 分析 ####

> 链表在首部增加节点时，可能会出现忘记将头节点head重新指向链表头部。解决方法可以在头部添加节点后，需要将新添加的节点重新指向head。
> 
> 在链表中间添加节点时，需要添加一个位置变量表示在中间的哪一个位置进行插入元素，这个位置变量由用户进行输入，用户可能会输入超过或少于链表长度范围的数，这时候，需要对位置变量进行限制。当用户设置的数在上述范围时，就直接报错或者直接提醒用户并返回头节点。其次，当这个位置变量等于1时，表示插入的位置在第一个节点，即为头插入。最后，在插入节点过程中，需要遍历找到要插入的位置，然后将当前位置接入到前驱节点和后继节点之间。但是到达了这个位置后却不能获取前驱节点了，也就无法将节点接入进来了，因此，需要在目标节点的前一个位置停下来，使用cur.next的值，而不是cur的值来判断。
> 
> 在尾部插入节点时，只需要循环遍历链表，将链表最后一个节点（该节点的next属性为null）重新指向要插入的新节点即可

#### 头部插入代码实现 ####

注意事项：头节点head需要重新指向链表头部

/**
         * 1. 头插入
         * @param head               当前链表的头节点
         * @param newNode       新的节点
         * @return                        新的链表的头节点
         */
        public Node insetSingleLikedHead(Node head , Node newNode){
    //        由于head为null时，新的节点就会变为head，因此不管有没有这部判断都可
    //        if (head == null){
    //            return newNode;
    //        }
            // 将当前链表头节点 作为 新节点的next属性（即将旧的头节点往后移）
            newNode.next = head;
            // 将新节点作为头节点
            head = newNode;
            return head;
        }

#### 中间插入代码实现 ####

注意事项：需要对用户输入的位置变量进行限制；需要在目标节点的前一个位置停下来，使用cur.next的值，而不是cur的值来判断。

/**
         * 2. 中间插入
         * @param head            当前链表的头节点
         * @param newNode    新的节点
         * @param position      节点插入的位置
         * @return                     新的链表的头节点
         */
        public Node insertSingleLinkedCenter(Node head,Node newNode,int position){
            // 获取链表长度
            int length = this.getLinkedListLength(head);
            // 插入元素不能在头节点之前，也不能在尾节点之后（尾节点.next）插入
            if (position < 1 || position > length +1){
                throw new RuntimeException("插入的位置违规");
            }
            // 头节点为null 时，将新的节点作为头节点返回即可
            if ( head == null){
                return newNode;
            }
            // 当插入位置为1，表示为头插入
            if (position == 1){
                newNode.next = head;
                head = newNode;
                return  head;
            }
            // 定义辅助节点进行遍历，避免头节点被覆盖
            Node node = head;
            // 设置 i 的初始值为 1，是为了确保在循环体内找到插入位置的前一个节点，准备进行插入操作
            // 如果 i 的初始值为 0，那么第一次循环迭代时，node = node.next 实际上是将指针从头节点移动到第二个节点，这样就无法找到插入位置的前一个节点了，而是直接定位到了插入位置的节点
            // i < position-1，表示循环执行的次数是插入位置减1次。这是因为要插入一个新节点，需要找到插入位置的前一个节点，即位置为 position-1 的节点。
            for (int i = 1; i < position-1; i++) {
                node = node.next;
            }
            // 如果直接交换位置，原来node指针的下一个节点就不见了，因此先让新节点的下一个指针接住node指针的下一个节点，确保其不消失
            newNode.next = node.next;
            node.next = newNode;
            return head;
        }

#### 尾部插入代码实现 ####

注意事项：头节点问题

/**
         * 3.尾插入
         * @param head          当前链表头节点
         * @param newNode   插入的新节点
         * @return                    新链表的头节点
         */
        public  Node insertSingleLinkedEnd(Node head , Node newNode){
            Node node = head;
            while (node.next != null){
                node = node.next;
            }
            node.next = newNode;
            return head;
        }

#### 综合插入代码实现（和中间插入实现差不多） ####

/**
         * 2. 综合插入
         * @param head            当前链表的头节点
         * @param newNode    新的节点
         * @param position      节点插入的位置
         * @return                     新的链表的头节点
         */
        public Node insetSingleLinked(Node head , Node newNode , int position){
            // 获取链表长度
            int length = this.getLinkedListLength(head);
            // 健壮性判断
            if (position < 1 || position > length + 1){
                throw new RuntimeException("节点插入的位置不合法");
            }
            if ( head == null){
                return newNode;
            }
            if (position == 1){
                newNode.next = head;
                head = newNode;
                return  head;
            }
            Node node = head;
            for (int i = 1; i < position - 1; i++) {
                node = node.next;
            }
            // 找到插入位置之后，便可以进行插入了
            newNode.next = node.next;
            node.next = newNode;
            return head;
        }

### 题目三：链表删除节点操作 ###

#### 问题 ####

> 链表删除节点，首部、中间和尾部分别会有什么问题，该如何处理？

#### 分析 ####

> 链表删除节点需要知道头节点和删除节点的位置。因此需要判断头节点是否为null（是否是空链表）和限制用户输入的节点位置。在限制用户输入的节点位置这方面，和插入节点的判断稍有不同，因为在插入节点时，需要知道要插入节点位置的前一个位置，因此需要判断插入节点位置的后一个位置是否大于链表的长度+1；而在删除节点时，只需要判断删除节点的当前位置即可，因此需要判断删除节点位置是否大于链表的长度即可。
> 
> 在删除节点时，如果删除节点的位置为1，表示首部删除，只需要将head的指针后移即可，即：head = head.next。当然，一般会使用辅助节点来承接头节点，对整个链表进行操作。
> 
> 除了首部删除之外，中间删除和尾部删除是可以同时判断的，因为在寻找删除位置时，需要找到删除位置的前一个位置，然后再用一个临时节点存储删除位置的节点，再将删除位置的前一个位置的节点指向临时节点的后一个位置即可。如果临时位置节点的下一个节点为null，则表示尾删除；如果不是null，则表示删除中间的节点。

#### 综合删除节点代码 ####

public Node deleteSingleListNode(Node head,int position){
            Node node = head;
            int length = this.getLinkedListLength(head);
            // 健壮性判断
            //当 position > length 时，表示要删除的位置大于链表的长度，换句话说，要删除的位置位于链表的末尾之后。在链表中并不存在这个位置，因此删除操作是无效的。
            // 如果采用 position > length + 1，则表示要删除的位置比链表的末尾之后还要远的位置，这样的删除操作同样是无效的。就只需要判断position > length即可
            if (position < 1 || position > length){
                throw new RuntimeException("节点删除的位置不合法");
            }
            if (head == null){
                return null;
            }
            // 头删除
            if (position == 1){
                node = head.next;
                return node;
            }else{
                //考虑到删除操作，我们需要找到要删除节点的前一个节点，以便将其 next 指针指向要删除节点的下一个节点，从而将要删除的节点从链表中移除。
                // 因此，当循环执行到第 position-1 个节点时，node 实际上指向了要删除节点的前一个节点。
                for (int i = 1 ; i < position - 1; i++) {
                    node = node.next;
                }
                // 定义一个节点来存储找到当前位置的节点，如果当前位置节点的下一个节点为null，则表示尾删除；如果不是null，则表示删除中间的节点
                Node curNode = node.next;
                node.next = curNode.next;
            }
         return head;
        }

### 修改链表节点 ###

> 修改链表节点需要知道头节点、修改的位置和修改的节点

/**
         *  链表修改
         * @param head                链表头节点
         * @param updateNode   要更新的节点
         * @param position          要更新的节点位置
         * @return                         新的链表头节点
         */
        public Node updateSingleLinkedList(Node head,int position,Node updateNode){
            int length = this.getLinkedListLength(head);
            // 健壮性判断
            if (position < 1 || position > length + 1){
                throw new RuntimeException("节点修改的位置不合法");
            }
            // 头节点为null，可以抛出异常，也可以将头节点的null改为updateNode
            if ( head == null){
                return updateNode;
            }
            Node node = head;
            for (int i = 1; i < position; i++) {
                node = node.next;
            }
            node.data = updateNode.data;
            return head;
        }

### 题目四：双向链表的构造 ###

> 双向链表其实就是在单链表的基础上添加了一个节点属性用来指向前一个节点，因此在构造节点方面，只需要添加一个prev节点属性即可

#### 节点构造 ####

// 双向链表
    public class DoubleNode {
        public int data;
        public DoubleNode prev;
        public DoubleNode next;
    
        public DoubleNode(int data) {
            this.data = data;
        }
    }

> 将数组转化为双向链表

数组转为双向链表的方法

public DoubleNode transformDoubleLinkedList(char [] arr){
            DoubleNode head = null;
            if (arr.length > 0){
                head = new DoubleNode(arr[0]);
            }
            DoubleNode node = head;
            for (int i = 1; i < arr.length; i++) {
                DoubleNode temp = new DoubleNode(arr[i]);
                node.next = temp;
                temp.prev = node;
                node = temp;
            }
            return head;
        }

双向链表的遍历方法

public void printDoubleLinkedList(DoubleNode head){
            while (head != null){
                System.out.print( head.data+"->");
                head = head.next;
            }
        }

运行测试方法

public static void main(String[] args) {
            char [] arr = {'a','c','w','x','y','h','x'};
            DoubleLinkedList linkedList = new DoubleLinkedList();
            DoubleNode head = linkedList.transformDoubleLinkedList(arr);
            linkedList.printDoubleLinkedList(head);
        }

> 双向链表新增节点

双向链表新增节点操作和单向链表新增节点操作差不多，只是在新增节点后，要将前驱节点设置为新增节点的前一个节点

#### 新增节点代码实现 ####

public DoubleNode insertDoubleNode(DoubleNode head,DoubleNode newDoubleNode,int position){
            DoubleNode doubleNode = head;
            // 获取链表长度
            int length = this.getDoubleLinkedListLength(head);
            // 判空
            if (head == null){
                return newDoubleNode;
            }
            // 限制position
            if (position < 1 || position > length+1){
                System.out.println("输入的节点位置有误");
                return head;
            }
            // 头插入
            if (position == 1){
                newDoubleNode.next = doubleNode;
                doubleNode.prev = newDoubleNode;
                head = newDoubleNode;
                return head;
            }
            // 具体位置插入
            for (int i = 1; i < position - 1; i++) {
                doubleNode = doubleNode.next;
            }
            newDoubleNode.next = doubleNode.next;
            newDoubleNode.prev = doubleNode;
            doubleNode.next = newDoubleNode;
            return head;
        }

> 双向链表删除节点操作

上代码

public DoubleNode deleteDoubleNode(DoubleNode head,int position){
            DoubleNode doubleNode = head;
            // 获取链表长度
            int length = this.getDoubleLinkedListLength(head);
            // 判空
            if (head == null){
                return null;
            }
            // 限制position
            if (position < 1 || position > length){
                System.out.println("输入的节点位置有误");
                return head;
            }
            // 头删除
            if (position == 1){
                head = head.next;
                head.prev = null;
                return head;
            }else {
                for (int i = 1; i < position -1; i++) {
                    doubleNode = doubleNode.next;
                }
                DoubleNode curDoubleNode = doubleNode.next;
                doubleNode.next = curDoubleNode.next;
            }
            return head;
        }

至此，链表青铜局结束

[3ba50564771a4d8bb3f1ec5987f65e77.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/9191fdf00b2b49fcb80ad7d63afde2d0.png