刷题日记 Day 3 : Leetcode 203 . 移除链表元素、Leetcode 707 . 设计链表、Lettcode 206 . 反转链表

一时失言乱红尘 2024-03-25 20:17 78阅读 0赞

#### 刷题日记 Day 3 ####

*  一 . Leetcode 203 . 移除链表元素
 *  二 . Leetcode 707 . 设计链表
 *  三 . Leetcode 206 . 反转链表

> 本篇文章 , 是在代码随想录 60 天编程挑战的基础上进行的题目讲解  
> 参与链接在此 : [https://programmercarl.com/other/xunlianying.html][https_programmercarl.com_other_xunlianying.html]

> 大家好 , 这个专栏 , 给大家带来的是 60 天刷题强训 . 最令大家头疼的事就是刷题了 , 题目又臭又长又抽象 , 有的题读都读不懂 , 更别说做了 . 所以 , 这个专栏想要帮助大家摆脱困境 , 横扫饥饿 , 做回自己 . 让大家掌握最常见的面试题 , 面对陌生的题目也不至于无从下手 .  
> 也希望大家监督 , 60 天从 0 到 1 , 咱们一起做大佬 ~  
> 今天是 Day3 , 大家加油~  
> ![image.png][]  
> 专栏链接 : [https://blog.csdn.net/m0\_53117341/category\_12247938.html?spm=1001.2014.3001.5482][https_blog.csdn.net_m0_53117341_category_12247938.html_spm_1001.2014.3001.5482]  
> 昨天的打卡链接 : [https://blog.csdn.net/m0\_53117341/article/details/129597675][https_blog.csdn.net_m0_53117341_article_details_129597675]

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

题目链接 : [203. 移除链表元素][203.]  
![image.png][image.png 1]  
这道题 , 在链表的题目中 , 算是简单题目 , 但是对于没接触过链表或者有一段时间没做链表习题的同学们来说 , 也不是一下子就能解决的  
那我给大家讲一下这道题  
![image.png][image.png 2]  
所以其实这道题 , 思路还是很清晰的 , 作为链表练手题还是绰绰有余的  
代码也给大家贴在这里了

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public ListNode removeElements(ListNode head, int val) {
        
            // 1. 参数判断
            if(head == null) {
        
                return null;
            }
    
            // 2. 定义 cur 指针、pre 指针
            // 让 cur 指针指向链表第二个节点
            // 让 pre 指针指向 cur 的前面,此时也就是第一个节点
            ListNode cur = head.next;
            ListNode pre = head;
    
            // 3. 让 cur 不断往后走,直到越界
            while(cur != null) {
        
                // 找到要删除的节点
                // 让前一个节点的 next 指向下一个节点
                // 然后 cur 继续往后走
                if(cur.val == val) {
        
                    pre.next = cur.next;
                    cur = cur.next;
                } else {
        
                    // 不是要删除的节点
                    // pre cur 指针正常往后走
                    pre = pre.next;
                    cur = cur.next;
                }
            }
    
            // 4. 特殊情况判断:如果第一个节点就是我们要删除的节点
            // 那就直接把头结点跳过,让头结点往后移动一下就好了
            if(head.val == val) {
        
                head = head.next;
            }
            return head;
        }
    }

但是上面的这种处理方法虽然与运行速度快 , 但是他需要额外考虑第一个节点是不是我们要删除的节点的问题  
我们还可以通过手动创建一个虚拟头结点来达到所有的节点处理方式都一样的效果  
![image.png][image.png 3]  
那来看虚拟头结点版本的代码

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public ListNode removeElements(ListNode head, int val) {
        
            // 1. 参数判断
            if(head == null) {
        
                return null;
            }
    
            // 2. 定义虚拟头结点
            ListNode tmpHead = new ListNode(-1);
            // 注意:要将虚拟头结点接到链表上
            tmpHead.next = head;
    
            // 3. 定义 cur 指针,刚开始让他指向 head 让他不断往后移动
            ListNode cur = head;
            // 4. 定义 pre 指针,刚开始让他指向 tmpHead(要在 cur 的前面)
            ListNode pre = tmpHead;
    
            // 5. 让 cur 不断往后走
            while(cur != null) {
        
                // 不是要删除的值的话,cur pre 就正常往后走
                if(cur.val != val) {
        
                    cur = cur.next;
                    pre = pre.next;
                } else {
        
                    // 是要删除的值的话,那就让前一个节点的next指向后一个节点
                    pre.next = cur.next;
                    // 删除完节点之后 cur 继续往后移动
                    cur = cur.next;
                }
            }
    
            // 最后返回虚拟头结点的 next(也就是 head)
            return tmpHead.next;
        }
    }

这样的话 , 今天的第一道题就轻轻松松~  
![image.png][image.png 4]

## 二 . Leetcode 707 . 设计链表 ##

题目链接 : [707. 设计链表][707.]  
![image.png][image.png 5]  
这道题其实挺麻烦的 , 大家需要耐心做下去 , 题目难度还可以 , 就是有很多非常细琐的小点  
![无标题.png][.png]

// 手动定义链表的节点类
    class ListNode {
        
        public int val;
        public ListNode next;
    
        public ListNode() {
        }
    
        public ListNode(int val) {
        
            this.val = val;
        }
    }
    
    class MyLinkedList {
        
    
        // 定义 size 表示链表长度
        public int size = 0;
    
        // 定义链表虚拟头结点
        public ListNode tmpHead;
    
        // 初始化
        public MyLinkedList() {
        
            // 最刚开始链表长度为0
            size = 0;
            // 实例化初识头结点
            tmpHead = new ListNode(0);
        }
        
        // 获取 index 下标的值
        public int get(int index) {
        
            // 注意 index 的合法性
            if(index < 0 || index >= size) {
        
                return -1;
            }
    
            // 定义 cur 指针,让他指向 head
            ListNode cur = tmpHead;
    
            // 注意:这里需要走 index+1 步才能到 index 的位置
            // 因为 index 是从 0 开始计算的
            while((index + 1) != 0) {
        
                cur = cur.next;
                index--;
            }
            return cur.val;
        }
        
        // 在指定节点处添加节点
        public void addAtIndex(int index, int val) {
        
            // 判断下标合法性
            if(index < 0 || index > size) {
        
                return;
            }
            // 添加元素,长度就要+1
            size++;
    
            // 定义cur指针当跑路者
            ListNode cur = tmpHead;
            while(index != 0) {
        
                cur = cur.next;
                index--;
            }
    
            // 走到了 index 的位置
            // 就可以插入元素了
            ListNode node = new ListNode(val);
            node.next = cur.next;
            cur.next = node;
        }
        
        // 在头节点处添加节点
        public void addAtHead(int val) {
        
            ListNode node = new ListNode(val);
            node.next = tmpHead.next;
            tmpHead.next = node;
            size++;
        }
        
        // 在尾结点处添加节点
        public void addAtTail(int val) {
        
            // 先找到尾结点
            ListNode cur = tmpHead;
            // 尾结点:cur.next为空
            while(cur.next != null) {
        
                cur = cur.next;
            }
            ListNode node = new ListNode(val);
            // 直接让尾结点的 next 接上新节点就可以
            cur.next = node;
            size++;
        }
    
        public void deleteAtIndex(int index) {
        
            // 判断下标合法性
            if(index < 0 || index >= size) {
        
                return;
            }
            // 删除元素,size要-1
            size--;
            ListNode cur = tmpHead;
    
            // 找到要删除的元素
            while(index != 0) {
        
                cur = cur.next;
                index--;
            }
            // 跳过这个元素
            cur.next = cur.next.next;
        }
    }
    
    /**
     * Your MyLinkedList object will be instantiated and called as such:
     * MyLinkedList obj = new MyLinkedList();
     * int param_1 = obj.get(index);
     * obj.addAtHead(val);
     * obj.addAtTail(val);
     * obj.addAtIndex(index,val);
     * obj.deleteAtIndex(index);
     */

恭喜你 , 又完成了一道题 ~  
![image.png][image.png 6]

## 三 . Leetcode 206 . 反转链表 ##

题目链接 : [206. 反转链表][206.]  
![image.png][image.png 7]  
其实这道题 , 应该算是许多人的链表初恋 , 许多人的链表第一题就是反转链表  
那么我们来看看咋回事  
![image.png][image.png 8]  
那记住这几个步骤 , 我们很容易的就可以写出 反转链表 的代码

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public ListNode reverseList(ListNode head) {
        
            if(head == null) {
        
                return null;
            }
    
            // 定义两个指针:pre next
            // 让他们都指向 null
            ListNode pre = null;
            ListNode next = null;
    
            // 定义 cur 指针,指向头结点
            // 这样做的原因是避免头指针被篡改,防止以后还需要
            ListNode cur = head;
    
            // 循环停止条件:cur走向空
            while(cur != null) {
        
                // 先让next保存下一个节点
                next = cur.next;
                // 让当前节点的next指针往前指
                cur.next = pre;
                // 将pre指向当前节点
                pre = cur;
                // cur往后移动
                cur = next;
            }
    
            // 走到最后的时候,最后一个节点就是新的头结点
            return pre;
        }
    }

[https_programmercarl.com_other_xunlianying.html]: https://programmercarl.com/other/xunlianying.html
[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/9a2af0a678ec4d05825e6750b6835654.png
[https_blog.csdn.net_m0_53117341_category_12247938.html_spm_1001.2014.3001.5482]: https://blog.csdn.net/m0_53117341/category_12247938.html?spm=1001.2014.3001.5482
[https_blog.csdn.net_m0_53117341_article_details_129597675]: https://blog.csdn.net/m0_53117341/article/details/129597675
[203.]: https://leetcode.cn/problems/remove-linked-list-elements/
[image.png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/565b2ac9a16e4ef58572e6ca215c8639.png
[image.png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/88bc61b4f2ce414c996f5f8eaef94038.png
[image.png 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/676bdfffab814237a4f0dfd327668b17.png
[image.png 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/453febef963c43b79059136fc49cfb29.png
[707.]: https://leetcode.cn/problems/design-linked-list/
[image.png 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/0136fb20014640c7b7d931ed4d99bd54.png
[.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/339644bd544c49839489c1efde712b20.png
[image.png 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/600fa47646e248f1b5f6582c64aa77e4.png
[206.]: https://leetcode.cn/problems/reverse-linked-list/
[image.png 7]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/7d2c099d864e43d79651f0ccc4cea6fb.png
[image.png 8]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/0e7630802a8a4baf858e164643162b55.png