Leetcode刷题day3|第二章链表1| 203.移除链表元素 ,707.设计链表 ,206.反转链表

不念不忘少年蓝@ 2024-03-31 08:17 57阅读 0赞

##  ##

#### 文章目录 ####

*  
 *   *  一、面试中链表的基本知识
     *   *  什么是链表
         *  链表的分类
         *  链表的存储方式
         *  链表的定义
         *  链表的操作
     *  二、移除链表元素
     *   *  双指针思路
         *  AC代码
         *  递归思路
         *  AC代码
     *  三、设计链表
     *   *  思路
         *  AC代码
     *  四、反转链表
     *   *  思路
         *  AC代码
     *  关于解题是不是用虚拟节点

### 一、面试中链表的基本知识 ###

#### 什么是链表 ####

定义：链表就是一种通过“指针”连在一起的线性结构。每个节点由由两部分组成，一个是数据域，一个是指针域。数据域中存放的是下一个节点的地址，最后一个节点的指针域指向null。但是具体数据域中是不是只有一个数据，指针域中只有一个指针，这个我们并没有规定。

#### 链表的分类 ####

根据方向分：单向、双向

根据循不循环分：循环，非循环

根据带不带头分：带头、不带头

所以总共有2^3种，但是并不是全部都常用。比较常用的是无头非循环单链表、无头 非循环双链表等。

#### 链表的存储方式 ####

先说结论：在内存中不是连续存储的。

链表是通过指针域的指针链接在内存中的各个节点，是散乱分布在内存的某些地址上，但是也有一定的概率连续存储。也可以说是链表的节点在内存中是随机存储的，可连续可不连续。

#### 链表的定义 ####

先说一下大体思路。定义一个链表结构，我们首先需要有一个链表节点，这个节点结构的定义在java中我们一般单独写一个类。对于链表，内部我们需要实现它的操作。至于这个节点类我们写在内部写在外部都可以，只不过如果是写成MyLinkedList的内部类，再测试类中调用的时候可能相对比较麻烦。下边我们写一下大概的轮廓。

这里我将它写成了外部类。

同时注意MyLinkedList应该怎么构造？

定义类属性size和head，在构造方法中赋值，如果想要虚拟头，就给head赋值为-1或者0,想要不带头的直接赋成null。

#### 链表的操作 ####

1.  删除节点

一般需要用到双指针，或者直接cur.next=cur.next.next;

1.  增加节点
    
    头插尾插不需要双指针，中间插入需要用到双指针。
2.  查找节点
    
    直接遍历
3.  更改节点值
    
    遍历更改

……

### 二、移除链表元素 ###

[题目链接][Link 1]

#### 双指针思路 ####

比较简单的一种方法，定义虚拟头结点

1.  双指针pre和cur
2.  定义临时变量curNext记录cur的下一个节点
3.  如果是cur是需要删除的节点
4.  curNext始终指向cur的下一个节点
5.  pre和curNext连接
6.  cur变成null，遍历结束

#### AC代码 ####

class Solution {
        
        public ListNode removeElements(ListNode head, int val) {
        
            ListNode tmp=new ListNode(-1);
            tmp.next=head;
            ListNode pre=tmp;
            ListNode cur=head;
            while(cur!=null){
        
                ListNode curNext=cur.next;
                if(cur.val==val){
        
                    pre.next=cur.next;
                }else{
        
                    pre=cur;
                }          
                cur=curNext;
            }
            return tmp.next;
        }
    }

#### 递归思路 ####

直接双指针改递归即可

#### AC代码 ####

class Solution {
        
        public ListNode reverseList(ListNode head) {
        
            if(head==null||head.next==null){
        
                return head;
            }
            ListNode newHead=reverseList(head.next);
            head.next.next=head;
            head.next=null;//一定注意这两个顺序
            return newHead;
        }
    }

### 三、设计链表 ###

[题目链表][Link 2]

#### 思路 ####

注意MyLinkedList构造方法怎么写

1.  MyLinkedList构造方法:在外部定义size和head，在内部进行初始化
2.  get:首先判断index是否合法，注意到底循环多少次(index是从0开始的)
3.  addAtHead、addAtTail都是基于addAtIndex完成的。addAtIndex也是需要判断坐标是否合法的，但是注意，他这里有个特殊处理，就是如果给定的坐标如果是负数，全部插入到0位置。这个跟我以前实现的是不一样的。
4.  删除指定下标的元素，首先判断坐标是否合法，之后找到需要删除的元素。但是这里没有用双指针而是直接通过`pre.next=pre.next.next;`完成的。

之前我也写了关于链表的总结，里边也有对无头非循环单链表的实现，那里边相对这里有些区别，比如说指定坐标插入元素时基于头插和尾插实现的，还有坐标合法性的判断，如果是负数，直接判定不合法，再比如节点是写成了内部类等等。

但无论哪种写法都是特别注意循环条件的判断到底是cur.next还是cur不为空以及插入节点的时候一定要先绑定后边的！！！。

#### AC代码 ####

class ListNode{
        
        int val;
        ListNode next;
        public ListNode(int val){
        
            this.val=val;
        }
    }
    class MyLinkedList {
        
        int size;
        ListNode head;
        public MyLinkedList() {
        
            size=0;
            head=new ListNode(0);
        }
        
        public int get(int index) {
        
            if(index<0||index>=size){
        
                return -1;
            }
            ListNode cur=head;
            while(index+1!=0){
        
                cur=cur.next;
                index--;
            }
            return cur.val;
        }
        
        public void addAtHead(int val) {
        
            addAtIndex(0,val);
        }
        
        public void addAtTail(int val) {
        
            addAtIndex(size,val);
        }
        
        public void addAtIndex(int index, int val) {
        
            if(index>size){
        
                return ;
            }
            index=Math.max(0,index);
            size++;
            ListNode pre=head;
            while(index--!=0){
        
                pre=pre.next;
            }
            ListNode node=new ListNode(val);
            node.next=pre.next;
            pre.next=node;
        }
        
        public void deleteAtIndex(int index) {
        
            if(index<0||index>=size){
        
                return ;
            }
            size--;
            ListNode pre=head;
            while(index--!=0){
        
                pre=pre.next;
            }
            pre.next=pre.next.next;
        }
    }

### 四、反转链表 ###

[题目链接][Link 3]

#### 思路 ####

1.  定义遍历变量cur，定义临时变量curNext,始终指向cur的下一个节点
2.  每次更改head的next域
3.  cur为空，结束循环
4.  返回head

#### AC代码 ####

class Solution {
        
        public ListNode reverseList(ListNode head) {
        
            if(head==null||head.next==null){
        
                return head;
            }
            ListNode cur=head.next;
            head.next=null;
            while(cur!=null){
        
                ListNode curNext=cur.next;
                cur.next=head;
                head=cur;
                cur=curNext;
            }
            return head;
        }
    }

### 关于解题是不是用虚拟节点 ###

一般而言我用的不是特别多。但是对于特征比较明显的有时候会用，比如这里的删除元素。但是目前不用，其实也可以锻炼解题思维。不做强制要求。

关于链表的设计构造方法可以初始成带头的，也可以初始化成不带头的。

基本上所有的链表题目，都可以采用使用头结点和不适用头结点，看个人喜好了。

[Link 1]: https://leetcode.cn/problems/remove-linked-list-elements/
[Link 2]: https://leetcode.cn/problems/design-linked-list/
[Link 3]: https://leetcode.cn/problems/reverse-linked-list/