代码随想录算法训练营第三天 |203.移除链表元素，707.设计链表，206.反转链表

快来打我* 2024-04-23 03:51 73阅读 0赞

#### 链表基础 ####

1、链表定义：

（1）链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。

（2）链表的入口节点称为链表的头结点也就是head。

2、链表类型：

单链表：上面说的就是单链表。

双链表：

单链表中的指针域只能指向节点的下一个节点。

双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

双链表 既可以向前查询也可以向后查询。

循环列表：

循环链表，顾名思义，就是链表首尾相连。

循环链表可以用来解决约瑟夫环问题。

3、**数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。**

链表是通过指针域的指针链接在内存中各个节点。

所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

#### 203.移除链表元素 ####

1、题目链接：[代码随想录][Link 1]

2、文章讲解：[代码随想录][Link 1]

3、视频讲解： [手把手带你学会操作链表 | LeetCode：203.移除链表元素\_哔哩哔哩\_bilibili][_ LeetCode_203._bilibili]

4、题目：

题意：删除链表中等于给定值 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 输出：\[\]

5、难点：两种方式：

*  **直接使用原来的链表来进行删除操作。**
 *  **设置一个虚拟头结点在进行删除操作。（推荐）**

6、遵循点：

##### 添加虚拟节点解法 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(1)
 *  **自己手撕时候，会把第14、16行写成head，导致不通过**

class Solution {
        // 添加虚拟头节点解法（推荐）
        public ListNode removeElements(ListNode head, int val) {
            // 如果链表为空，直接返回（涉及到链表的，基本都要判断是否为空）
            if (head == null) {
                return null;
            }
            // 设置虚拟头结点，将虚拟节点的next指针指向head
            ListNode dumy = new ListNode(-1, head);
            ListNode pre = dumy;
            // 定义要操作的节点
            ListNode cur = head;
            // 遍历链表，删除指定值的节点
            while (cur != null) {
                // 如果当前节点的值等于要删除的值，就删除当前节点，将当前节点的next指针指向下下个节点
                if (cur.val == val) {
                    pre.next = cur.next;
                } else {
                    // 如果当前节点的值不等于要删除的值，就将pre指针后移一位，将cur指针后移一位
                    pre = cur;
                }
                // 将cur指针后移一位
                cur = cur.next;
            }
            // 返回虚拟头节点的next指针，即删除了指定值的链表头节点
            return dumy.next;
        }
    }

#### 707. 设计链表 ####

1、题目链接：[代码随想录][Link 2]

2、文章讲解：[代码随想录][Link 2]

3、视频讲解：[帮你把链表操作学个通透！LeetCode：707.设计链表\_哔哩哔哩\_bilibili][LeetCode_707._bilibili]

4、题目：

在链表类中实现这些功能：

*  get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
 *  addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
 *  addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
 *  addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
 *  deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

5、注意点：

**链表操作的两种方式：**

1.  直接使用原来的链表来进行操作。
2.  设置一个虚拟头结点在进行操作。（推荐）

6、知识点：head = new ListNode(0)和head = new ListNode()区别

在Java中，ListNode通常是一个用于表示链表节点的类，具有一个整数值（或其他数据类型）和指向下一个节点的引用。对于以下两种初始化链表头节点的方式：

head = new ListNode(0)

这行代码创建了一个新的ListNode对象，并将其初始值（val）设置为0，同时下一个节点（next）默认被初始化为null。当你需要立即创建一个带有特定值（这里是0）的链表节点时，这种方式非常有用。在处理链表问题时，常常用0或特殊的占位值作为哨兵节点，来简化边界条件的处理。

head = new ListNode()

如果ListNode类没有无参数构造器或者没有显示定义构造器，这将会导致编译错误，因为没有匹配的构造函数可以调用。但如果ListNode类有一个默认的无参构造器，那么这行代码将创建一个新的ListNode对象，其值（val）默认初始化为其类型的默认值（对于int是0，对于引用类型是null），并且next属性同样会被初始化为null。然而，在实际处理链表时，这种形式不常见，除非你确实想创建一个空值节点，并且该节点的值不需要有特殊含义。

总结来说，在处理链表时，**head = new ListNode(0)更常见**，因为它明确地设置了节点的值，而head = new ListNode()仅在你需要无初始值的新节点时使用，并且类提供了无参构造函数支持这种情况。

##### 单链表解法 #####

*  时间复杂度: 涉及 index 的相关操作为 O(index), 其余为 O(1)
 *  空间复杂度: O(n)

// 单链表解法
    class ListNode {
        int val;
        ListNode next;
    
        ListNode() {
        }
    
        ListNode(int val) {
            this.val = val;
        }
    }
    
    class MyLinkedList {
        // size存储链表元素的个数
        int size;
        // 虚拟头结点
        ListNode head;
    
        // 初始化链表
        public MyLinkedList() {
            size = 0;
            head = new ListNode(0);
        }
    
        // 获取第index个节点的数值，注意index是从0开始的，第0个节点就是头结点
        public int get(int index) {
            // 如果index非法，返回-1
            if (index < 0 || index >= size) {
                return -1;
            }
            ListNode currentNode = head;
            // 包含一个虚拟头节点，所以查找第 index+1 个节点
            for (int i = 0; i <= index; i++) {
                currentNode = currentNode.next;
            }
            return currentNode.val;
        }
    
        // 在链表最前面插入一个节点，等价于在第0个元素前添加
        public void addAtHead(int val) {
            addAtIndex(0, val);
        }
    
        // 在链表的最后插入一个节点，等价于在(末尾+1)个元素前添加
        public void addAtTail(int val) {
            addAtIndex(size, val);
        }
    
        // 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
        // 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点
        // 如果 index 大于链表的长度，则返回空
        public void addAtIndex(int index, int val) {
            if (index > size) {
                return;
            }
            if (index < 0) {
                index = 0;
            }
            size++;
            // 找到要插入节点的前驱
            ListNode pred = head;
            for (int i = 0; i < index; i++) {
                pred = pred.next;
            }
            ListNode toAdd = new ListNode(val);
            toAdd.next = pred.next;
            pred.next = toAdd;
        }
    
        // 删除第index个节点
        public void deleteAtIndex(int index) {
            if (index < 0 || index >= size) {
                return;
            }
            size--;
            if (index == 0) {
                head = head.next;
                return;
            }
            ListNode pred = head;
            for (int i = 0; i < index; i++) {
                pred = pred.next;
            }
            pred.next = pred.next.next;
        }
    }

##### 双链表解法 #####

// 双链表解法
    class ListNode {
        int val;
        ListNode next, prev;
    
        ListNode() {
        }
        
        ListNode(int val) {
            this.val = val;
        }
    }
    
    
    class MyLinkedList {
    
        // 记录链表中元素的数量
        int size;
        // 记录链表的虚拟头结点和尾结点
        ListNode head, tail;
    
        public MyLinkedList() {
            // 初始化操作
            this.size = 0;
            this.head = new ListNode(0);
            this.tail = new ListNode(0);
            // 这一步非常关键，否则在加入头结点的操作中会出现null.next的错误！！！
            head.next = tail;
            tail.prev = head;
        }
    
        public int get(int index) {
            // 判断index是否有效
            if (index < 0 || index >= size) {
                return -1;
            }
            ListNode cur = this.head;
            // 判断是哪一边遍历时间更短
            if (index >= size / 2) {
                // tail开始
                cur = tail;
                for (int i = 0; i < size - index; i++) {
                    cur = cur.prev;
                }
            } else {
                for (int i = 0; i <= index; i++) {
                    cur = cur.next;
                }
            }
            return cur.val;
        }
    
        public void addAtHead(int val) {
            // 等价于在第0个元素前添加
            addAtIndex(0, val);
        }
    
        public void addAtTail(int val) {
            // 等价于在最后一个元素(null)前添加
            addAtIndex(size, val);
        }
    
        public void addAtIndex(int index, int val) {
            // index大于链表长度
            if (index > size) {
                return;
            }
            // index小于0
            if (index < 0) {
                index = 0;
            }
            size++;
            // 找到前驱
            ListNode pre = this.head;
            for (int i = 0; i < index; i++) {
                pre = pre.next;
            }
            // 新建结点
            ListNode newNode = new ListNode(val);
            newNode.next = pre.next;
            pre.next.prev = newNode;
            newNode.prev = pre;
            pre.next = newNode;
    
        }
    
        public void deleteAtIndex(int index) {
            // 判断索引是否有效
            if (index < 0 || index >= size) {
                return;
            }
            // 删除操作
            size--;
            ListNode pre = this.head;
            for (int i = 0; i < index; i++) {
                pre = pre.next;
            }
            pre.next.next.prev = pre;
            pre.next = pre.next.next;
        }
    }

#### 206、反转列表 ####

1、题目链接：[代码随想录][Link 3]

2、文章讲解：[代码随想录][Link 3]

3、视频讲解：[帮你拿下反转链表 | LeetCode：206.反转链表 | 双指针法 | 递归法\_哔哩哔哩\_bilibili][_ LeetCode_206._ _ _ _ _bilibili]

4、题目：

题意：反转一个单链表。

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

5、难点：

如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。

其实只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表

6、思路：

首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。

然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。

为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。

接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。

最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点

**双指针解法**

*  时间复杂度 O(n)
 *  空间复杂度 O(1)

class Solution {
        public ListNode reverseList(ListNode head) {
            // 双指针法
            // 定义两个指针，一个指向前一个节点，一个指向当前节点
            ListNode pre = null;
            ListNode cur = head;
            // 临时变量，用于保存当前节点的下一个节点
            ListNode temp = null;
            while (cur != null) {
                // 将当前节点的下一个节点保存到临时变量中，然后将当前节点的next指针指向前一个节点，然后前一个节点指向当前节点，然后将当前节点指向临时变量，继续循环
                temp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = temp;
            }
            return pre;
        }
    }

**递归解法**

*  时间复杂度: O(n), 要递归处理链表的每个节点
 *  空间复杂度: O(n), 递归调用了 n 层栈空间

class Solution {
        public ListNode reverseList(ListNode head) {
            // 递归解法
            return reverse(null, head);
        }
    
        private ListNode reverse(ListNode prev, ListNode cur) {
            if (cur == null) {
                return prev;
            }
            // 临时节点
            ListNode temp = cur.next;
            // 反转
            cur.next = prev;
            return reverse(cur, temp);
        }
    }

[Link 1]: https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html
[_ LeetCode_203._bilibili]: https://www.bilibili.com/video/BV18B4y1s7R9
[Link 2]: https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html
[LeetCode_707._bilibili]: https://www.bilibili.com/video/BV1FU4y1X7WD
[Link 3]: https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html
[_ LeetCode_206._ _ _ _ _bilibili]: https://www.bilibili.com/video/BV1nB4y1i7eL