• 【Java力扣《代码随想录》】第4章链表63-69题（leetcode题号203+707+206+24+19+面试题02.07+142）

    目录

    链表基础知识

    参考自《代码随想录》
    参考自Java链表详解
    参考自Java中链表的头结点

    链表的结构和存储方式

    在这里插入图片描述
    下面是一个5个节点的单链表。
    在这里插入图片描述

    链表的存储方式
    在这里插入图片描述

    Java中链表的分类

    • 单向链表，双向链表
    • 带头链表，不带头链表
    • 循环的，非循环的
      排列组合后一共有8种链表，其中单向、不带头、非循环以及双向、不带头、非循环的链表最为重要。
      Java的核心就是面向对象编程，因此我们可以把链表看成一个对象。我们可以定义一个类，ListNode，属性next（下一节点的引用），value（存储当前节点的值）

    1.单链表和双链表

    在这里插入图片描述
    单链表定义

    class ListNode {
    int val;
    ListNode next;//引用指向下一节点
    ListNode(int x) {//自定义有参构造方法
        val = x;
        this.next = null;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    java链表结点各种不同的构造方法

    public class ListNode {
    // 结点的值
    int val;

    // 下一个结点
    ListNode next;

    // 节点的构造函数(无参)
    public ListNode() {
    }

    // 节点的构造函数(有一个参数)
    public ListNode(int val) {
        this.val = val;
    }

    // 节点的构造函数(有两个参数)
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    链表就是多个对象之间引用起来，new出头结点后，把头结点的next引用新的节点即可完成链表创建，实际上链表就是多个链表对象串联起来
    单链表创建

    this.head = new ListNode(0);
head.next = new ListNode(1);

    • 1
    • 2

    在这里插入图片描述
    双向链表定义
    也是创建一个对象，双向链表与单向链表的区别就是当前节点可以指向前一个节点，同理存在一个prev引用，因此优势在于可以从后向前遍历链表。

    class ListNode {
    int val;
    ListNode next;
    ListNode prev;
    ListNode(int x) {
        val = x;
        this.prev = null;
        this.next = null;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    双向链表的创建
    双向链表创建时与单向链表一致，每个节点next引用下一个节点，同时当前节点prev引用前一个节点。

    this.head = new ListNode(0);
ListNode curr = new ListNode(1);
head.next = curr；
curr.prev = this.head;

    • 1
    • 2
    • 3
    • 4

    2.带头结点和不带头结点链表

    带头结点的链表指，链表的第一个节点不存储内容，只指向首节点1的指针。val为空，head.next.val = 1。即head的下一个节点才是1的节点

    不带头结点的链表指把头节点默认为首节点。也就是说head不仅指向1，而且head.val=1，那head.next.val=2。
    如图，两个1->2->3的单链表，带头结点和不带头结点的区别
    在这里插入图片描述

    带头结点的链表的优点在于，可以把链表中的所有结点当做同一类型的节点进行操作，在增删改查时无需判断是否为头结点。

    3.循环链表

    在这里插入图片描述

    链表的操作（单链表为例，分带头结点和不带）

    1.创建结点类

    节点由val域(数据域)，以及next域(指针域)组成，对于next域，其是引用类型，存放下一个节点的地址，故用ListNode next来创建next。
    同时设置构造函数，方便对val进行初始化。

    //单链表结点
class ListNode{
    int val;
    ListNode next;
    ListNode(){
        this.next = null;
    }
    ListNode(int x){
        val = x;
        this.next = null;
    }
    ListNode(int x,ListNode next){
        val = x;
        this.next = next;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    2.创建链表

    方法一：枚举法public void creatList()
    先创建一堆结点，再依次进行连接

    • 不带头结点的：
    	 //1.枚举法
    public void creatList(){
        ListNode now1 = new ListNode(1);
        ListNode now2 = new ListNode(2);
        ListNode now3 = new ListNode(3);
        ListNode now4 = new ListNode(4);

        this.head = now1;

        now1.next = now2;
        now2.next = now3;
        now3.next = now4;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 带头结点的：
      //1.枚举法
    public void creatList(){
        ListNode now1 = new ListNode(6);
        ListNode now2 = new ListNode(7);
        ListNode now3 = new ListNode(8);
        ListNode now4 = new ListNode(9);

        this.head.next = now1;

        now1.next = now2;
        now2.next = now3;
        now3.next = now4;

    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    方法二：头插法public void addFirst(int data)
    头插法是指在链表的头节点的位置插入一个新节点，定义一个newNode表示该新节点，新节点将原来的链表连接到其后，即连接原来的头结点。再将新节点作为新的头结点。
    对node的next进行赋值，用node.next = this.head进行连接，然后head指向新节点node

    • 不带头结点的：
      头指针指向新节点head = newNode;
      不带头结点的链表类中定义头结点为空指针，public ListNode head;
       //2.头插法
    public void addFirst(int data){
        ListNode newNode = new ListNode(data);
        newNode.next = this.head;//包含头指针为空的情况
        this.head = newNode;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 带头结点的：
      头指针的后继结点指向新节点 head.next = newNode;
      也无需考虑head == null的情况，因为带头结点的链表类定义的头结点不是空指针而是结点的无参构造public ListNode head = new ListNode();
     //2.头插法
    public void addFirst(int data){
        ListNode newNode = new ListNode(data);
        newNode.next = head.next;
        head.next = newNode;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    方法三：尾插法public void addLast(int data)
    尾插法是指在链表的尾节点的位置插入一个新节点，定义一个node表示新节点，定义结点cur遍历链表，走到尾部最后一个结点时，将新节点连接到其后。

    • 不带头结点的：
      特殊情况，链表为空head == null，尾插变为头插
     //3.尾插法
    public void addLast(int data){
        ListNode newNode = new ListNode(data);
        ListNode cur = this.head;
        //处理头结点为空的情况
        if(cur == null){
            this.head = newNode;
        }
        else{
            while(cur.next != null){
                cur = cur.next;
            }
            cur.next = newNode;
        }
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 带头结点的：
      不存在head == null的情况，head.next == null 与平常尾插无异
       //3.尾插法
    public void addLast(int data){
        ListNode newNode = new ListNode(data);
        //此时head一定不为空指针，因为带头结点的head是无参构造
        ListNode cur = head;
        while(cur.next != null){
            cur = cur.next;
        }
        cur.next = newNode;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    3.打印链表 public void display()

    • 不带头结点的：
      从头结点head开始打印
     //4.打印链表
    public void display(){
        ListNode cur = this.head;
        while(cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 带头结点的：
      从head.next开始打印
     //4.打印链表
    public void display(){
        ListNode cur = this.head.next;
        while(cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    4.查找关键字key是否在链表中，返回存在个数public int contains(int key)

    • 不带头结点的：
      从head开始查找
      head == null的情况，不进入while循环，返回count = 0
     //5.查找key在链表中的存在个数
    public int contains(int key){
        ListNode cur = this.head;
        int count = 0;
        while(cur != null){
            if(cur.val == key){
                count++;
            }
            cur = cur.next;
        }
        return count;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 带头结点的：
      从head.next开始查找
      head.next == null时不进入循环，返回count = 0
      //5.查找key存在个数
    public int contains(int key){
        ListNode cur = this.head.next;
        int count = 0;
        while(cur != null){
            if(cur.val == key){
                count++;
            }
            cur = cur.next;
        }
        return count;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    5.返回链表长度 public int listSize()

    • 不带头结点的：
      head == null 不进入循环，返回Size == 0
      public int listSize(){
        ListNode cur  = this.head;
        int Size = 0;
        
        while(cur != null){
            Size++;
            cur = cur.next;
        }
        return Size;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 带头结点的：
      head.next == null 不进入循环，返回Size = 0
      public int listSize(){
        ListNode cur = this.head.next;
        int Size = 0;
        
        while(cur != null){
            Size++;
            cur = cur.next;
        }
        return Size;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    6.链表任意位置插入（第一个数据节点默认下标为0）public boolean addIndex(int index, int data)，写辅助方法 public ListNode searchIndex(int index)找到index位置的前一个结点并返回

    在这里插入图片描述
    注意：插入结点前，要先连接F->D,再C->F，以免丢失D之后的链表
    因为C->F时C->D的链断裂。

    • 不带头结点的：
      链表：1->2->5->5
      下标：0, 1, 2, 3
      • 查找index索引的前驱结点时
        空链表找不到任何索引index的前驱结点
        非空链表，如果索引 <= 0或 > listSize()则找不到前驱
        index = listSize()时，结点并不存在，但存在他的前驱结点为链表的末尾结点。
      • 插入结点时
        特殊情况，空链表head == null时，只有index = 0可以当做是头插进行插入操作，别的索引都不在空链表中存在，不可插入。
        index = 0时，需插入的位置为头结点，不存在前驱结点,进行特殊处理，头插。
        判断前驱结点cur == null说明不可插入，返回false。
        其余普通情况查找到index索引的前驱结点后，进行插入操作即可，插入成功返回true。
    //7.2找到索引index的前一个节点，链表中首个数据节点下标为0，索引为0或超出链表长度范围返回null
 public ListNode searchIndex(int index) {
        if(this.head == null){
            return null;
        }

        ListNode cur = this.head;
        int i = 1;//cur指向头结点，下标0。索引i指向cur的后一个节点与index比较
        if(index <= 0 || index > listSize()){
            return null;
        }
        
        while(i < index){
            cur = cur.next;
            i++;
        }
        return cur;//一定不为null可以找到
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
     //8.任意位置插入节点，第一个数据节点默认下标0
    public boolean addIndex(int index, int data){
        if(this.head == null && index != 0){//空链表没有结点，只有index为0时才可以插入，相当于头插
            return false;
        }

        ListNode cur = this.head;//寻找要插入的位置的前一个结点
        ListNode newNode = new ListNode(data);

        if(index == 0){
            //头插属于特殊情况，中间插入要得到插入位置的前一个结点。
            newNode.next = this.head;
            this.head = newNode;
            return true;
        }

        //寻找要index位置的前一个节点
        cur = searchIndex(index);
        //此时cur正在要插入节点位置的前一位
        if(cur != null){
            newNode.next = cur.next;
            cur.next = newNode;
            return true;
        }
        return false;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 带头结点的：
      链表：head->1->2->5->5
      下标：-1, 0, 1, 2, 3
      • 查找index索引的前驱结点时
        如果索引 < 0或 > listSize()则找不到前驱
        空链表，但是 index = 0 时，可以找到前驱结点为head头结点，但是空链表的其余index情况找不到前驱
        index = listSize()时，结点并不存在，但存在他的前驱结点为链表的末尾结点。
        让索引i遍历链表时保持在cur的后驱结点上，i与index相等时说明找到了index指向的结点，返回前驱cur
      • 插入结点时
        空链表或index == 0 的情况都可以找到前驱结点，无需特殊处理
        判断前驱结点cur == null说明不能插入
        其余普通情况查找到index索引的前驱结点后，进行插入操作即可。
     //7.2找到索引index的前一个节点，链表中首个数据节点下标为0，索引超出链表长度范围返回null
    public ListNode searchIndex(int index) {
      	if(this.head.next == null && index != 0){
            return null;
        }
        
        int i = 0;
        ListNode cur = this.head;//为i所指的前一个结点
        if(index < 0 || index > listSize()) {
            return null;
        }

        while(i < index) {
            cur = cur.next;
            i++;
        }
        return cur;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
     //8.任意位置插入节点，第一个数据结点默认下标0
    public boolean addIndex(int index, int data){   
        ListNode newNode = new ListNode(data);
        ListNode cur = searchIndex(index);

        if(cur != null) {
            newNode.next = cur.next;
            cur.next = newNode;
            return true;
        }
        return false;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    7.删除第一个值为key的结点public boolean remove(int key)写辅助方法 public ListNode searchKey(int key)找到值为key的前一个结点并返回

    在这里插入图片描述

    • 不带头结点的：
      • 查找值为key结点的前驱结点
        空链表或头结点head == key的情况下找不到前驱结点
        遍历链表，找到key后返回前驱，找不到返回空指针
      • 删除key值结点
        特殊处理：空链表没得删，头指针head == key进行头删
        普通情况：找到key前驱结点后删除，找不到说明没得删
    //7.1找到key值的前一个结点,key在首位或不存在返回null
    public ListNode searchKey(int key){
        if(this.head == null){
            return null;
        }

        ListNode cur = this.head;
        if(cur.val == key){
            return null;//头结点为key找不到头结点的前一个节点
        }

        while(cur.next != null){
            if(cur.next.val == key) {
                return cur;
            }else{
                cur = cur.next;
            }
        }
        return null;//如果找不到则是越界为null
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
     //9.删除第一次出现关键字为key的节点
    public boolean remove(int key){//删除成功返回真,没有可删除的则返回假
        if(this.head == null){
            return false;
        }
        ListNode cur = this.head;
        //删除头结点的特殊情况
        if(cur.val == key){
            this.head = cur.next;
            return true;
        }

        //找key的前一个结点
        cur = searchKey(key);
        if(cur != null){
            cur.next = cur.next.next;
            return true;
        }
        return false;//链表里没有key

    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 带头结点的：
      • 查找值为key结点的前驱结点
        空链表找不到keycur.next == null 不进入循环，返回null;
        首个数据结点== key的情况下可找到前驱结点head
        遍历链表，找到key后返回前驱，找不到返回空指针
      • 删除key值结点

    普通情况：空链表没得删，找到的cur为null；找到key前驱结点后删除，找不到说明没得删

    //7.1找到第一次出现的key值的前一节点,没有key存在则返回null
    public ListNode searchKey(int key) {
        ListNode cur = this.head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                return cur;
            } else {
                cur = cur.next;
            }
        }
        return null;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
      //9.删除第一次出现关键字为key的节点：
    public boolean remove(int key){
        ListNode cur = this.head;
        cur = searchKey(key);

        if(cur != null){
            cur.next = cur.next.next;
            return true;
        }
        return false;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    8.删除所有值为key的结点public void removeAllKey(int key)

    key结点有两种情况，连续or不连续
    用cur指向不为key的结点，判断cur.next是否为key,若是则删除，若不是再移动cur = cur.next

    • 不带头结点的：
      需要区分头结点head是否为key的特殊情况，如果head.val一直为key,则持续进行头删。否则cur才开始遍历下一个结点
      非头结点的情况，判断cur.next是否为key如果是则删掉cur.next，否则cur再向后走。
    //10.删除所有值为key的节点：
    public boolean removeAllKey(int key){
        if(this.head == null){
            return false;
        }
        ListNode cur = this.head;
        boolean flag = false;
        //头结点为key
        while(cur.val == key){
            this.head = head.next;
            cur = this.head;
            flag = true;
        }
        //cur走到了新的头，并且不为key
        while(cur.next != null){
            if(cur.next.val == key){
                cur.next = cur.next.next;
                flag = true;
            }else{
                cur = cur.next;
            }
        }
        return flag;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 带头结点的：
      空链表无需进入循环，直接越过返回false
      cur恰好从头结点开始检查cur.next是否为key
     //10.删除所有值为key的节点：
    public boolean removeAllKey(int key){
        ListNode cur = this.head;
        boolean flag = false;
        while(cur.next != null){
            if(cur.next.val == key){
                cur.next = cur.next.next;//删了一位挪上来的下一位不确定是不是还是key，所以继续走循环检查
                flag = true;
            }else{
                cur = cur.next;//只有下一项不用删才走动。
            }
        }
        return flag;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    9.更改链表中第index个结点的值为data（首个数据节点下标默认0） public boolean changeIndex(int index, int data)

    空链表没有数据结点，无需查找更改

    • 不带头结点
     public boolean changeIndex(int index, int data){
        if(index < 0 || index = listSize()){//不能更改不存在的结点
            return false;
        }

        ListNode cur = this.head;
        int i = 0;//更改index位置，所以i与cur同步
        while(cur != null){
            if(i == index){
                cur.val = data;
                return true;
            }
            cur = cur.next;
            i++;
        }
        return false;//不可能走到这一步，因为不符合的情况开头已经排除
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 带头结点
     //11.更改链表中第index个结点的值为data（首个数据节点下标默认0）
    public boolean changeIndex(int index, int data){
        if(index < 0 || index >= listSize()){
            return false;
        }

        int i = 0;//i与cur保持在同一个结点
        ListNode cur = this.head.next;

        while(cur != null){
            if(i == index){
                cur.val = data;
                return true;
            }else{
                cur = cur.next;
                i++;
            }
        }

        return false;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    10.更改链表中第一个key值为data，public boolean changeKey(int key, int data)

    查找到key后更改，然后返回

    • 不带头结点
     //12.更改链表中第一个key值为data
    public boolean changeKey(int key, int data){
        ListNode cur = this.head;
        while(cur != null){
            if(cur.val == key){
                cur.val = data;
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 带头结点
    //12.更改链表中第一个key值为data
    public boolean changeKey(int key, int data){
        ListNode cur = head.next;
        while(cur != null){
            if(cur.val == key){
                cur.val = data;
                return true;
            }else{
                cur = cur.next;
            }
        }

        return false;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    11.更改链表中所有key为data， public boolean changeAllKey(int key, int data)

    查找到key后更改，继续遍历

    • 不带头结点
     //13.更改链表中所有key为data
    public boolean changeAllKey(int key, int data){
        ListNode cur = this.head;
        boolean flag = false;
        while(cur != null){
            if(cur.val == key){
                cur.val = data;
                flag = true;
            }
            cur = cur.next;
        }
        return flag;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 带头结点
    //13.更改链表中所有key为data
    public boolean changAllKey(int key, int data){
        ListNode cur = head.next;
        boolean flag = false;
        while(cur != null){
            if(cur.val == key){
                cur.val = data;
                flag = true;
            }
            cur = cur.next;
        }

        return flag;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    12.清空链表，public void clear()

    暴力方法，直接让head == null
    细致做法，每一个结点都置为null

    • 不带头结点的单链表
    public void clear(){
        ListNode cur = this.head;
        while(this.head != null){
            cur = head.next;
            this.head = null;
            this.head = cur;
        }
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 带头结点的单链表
    //14.清空链表：
    public void clear(){
        ListNode cur = head.next;
        while(head.next != null){
            cur = head.next;
            this.head = null;
            this.head = cur;
        }
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    在这里插入图片描述
    链表使用注意事项
    1、一定检查null，防止空指针，

    2、一定要防止环形出现，节点被多次使用，一定要备份，

    3、断开不必要指针。

    链表操作源码，单链表，带头结点的单链表，main函数调用

    //创建结点类
//main函数调用单链表和带头单链表的方法
package com.qxcto;
/**
 * @author xuexuezi
 * @IDE IntelliJ IDEA
 * @project_name Carl链表定义结点，main函数
 * @filename TestJuly_21
 * @date 2022/07/22
 */
class ListNode{
    int val;
    ListNode next;
    ListNode(){
        this.next = null;
    }
    ListNode(int x){
        val = x;
        this.next = null;
    }
    ListNode(int x,ListNode next){
        val = x;
        this.next = next;
    }
}
class DoubleNode{
    int val;
    DoubleNode prev;
    DoubleNode next;
    DoubleNode(int x){
        val = x;
        this.prev = null;
        this.next = null;
    }
}
//主函数所在方法
public class TestJuly_21 {
    public static void main(String[] args){
        //练习建立链表，

        //不带头结点的单链表
        System.out.println("不带头结点的单链表");
        MySingleLinkedList link1 = new MySingleLinkedList();

        //1.枚举法
        System.out.println("枚举法连接结点1,2,3,4");
        link1.creatList();

        //4.打印链表
        link1.display();
        System.out.println("头插3,2,3,4");
        //2.头插法
        link1.addFirst(3);
        link1.addFirst(2);
        link1.addFirst(3);
        link1.addFirst(4);

        link1.display();
        //3.尾插法
        System.out.println("尾插5,3,7,3");
        link1.addLast(5);
        link1.addLast(3);
        link1.addLast(7);
        link1.addLast(3);
        link1.display();
        //5.查找key在链表中存在几个
        int nums = link1.contains(3);
        System.out.println("3在链表中有 "+nums+" 个");
        //6.链表长度
        int listSize = link1.listSize();
        System.out.println("链表长度"+listSize);
        //8.任意位置插入
        System.out.println("在0位置插入3，在链表长度位置插入3");
        link1.addIndex(0,3);
        link1.addIndex(link1.listSize(),3);
        link1.display();
        //9.删除第一个key出现的结点
        link1.remove(3);
        System.out.println("删除第一个3");
        link1.display();
        //10.删除所有key
        link1.removeAllKey(3);
        System.out.println("删除所有3");
        link1.display();
        //11.改变index位置的值
        System.out.println("位置0改为200，位置100改为3，位置4改为44");
        link1.changeIndex(0,200);
        link1.changeIndex(100,3);
        link1.changeIndex(4,44);
        link1.display();
        //12.改key为data一次
        System.out.println("改7为777一次");
        link1.changeKey(7,777);
        link1.display();
        //13.改key为data
        System.out.println("改所有2为222");
        link1.changeAllKey(2,222);
        link1.display();
        //14.清空
        System.out.println("清空不带头结点的单链表link1");
        link1.clear();
        link1.display();




        //带头结点的单链表
        System.out.println("带头结点的单链表链表");
        MyHeadSingleLinkedList link2 = new MyHeadSingleLinkedList();
        //1.枚举
        System.out.println("枚举连接6,7,8,9");
        link2.creatList();
        //4.打印
        link2.display();
        //2.头插
        System.out.println("头插5,7,4,7");
        link2.addFirst(5);
        link2.addFirst(7);
        link2.addFirst(4);
        link2.addFirst(7);

        link2.display();
        //3.尾插
        System.out.println("尾插5,6,7,7");
        link2.addLast(5);
        link2.addLast(6);
        link2.addLast(7);
        link2.addLast(7);

        link2.display();
        //5.查找key在链表中存在几个
        int num2 = link2.contains(7);
        System.out.println("7在不带头链表中有 "+num2 +"个");
        //6.链表长度
        int listSize2 = link2.listSize();
        System.out.println("不带头链表长度 "+listSize2);
        //8.任意位置插入
        System.out.println("在0位置插入7，在链表长度位置插入67,链表长度位置再插入7");
        link2.addIndex(0,7);
        link2.addIndex(link2.listSize(),67);
        link2.addIndex(link2.listSize(),7);
        link2.display();
        //9.删除第一个key出现的结点
        link2.remove(7);
        System.out.println("删除第一个7");
        link2.display();
        //10.删除所有key
        link2.removeAllKey(7);
        System.out.println("删除所有7");
        link2.display();
        //11.改变index位置的值
        System.out.println("位置0改为6，位置10改为3，位置4改为444");
        link2.changeIndex(0,6);
        link2.changeIndex(10,3);
        link2.changeIndex(4,5);
        link2.display();
        //12.改key为data一次
        System.out.println("改6为666一次");
        link2.changeKey(6,666);
        link2.display();
        //13.改key为data
        System.out.println("改所有5为555");
        link2.changeAllKey(5,555);
        link2.display();
        //14.清空
        System.out.println("清空不带头结点的单链表link2");
        link2.clear();
        link2.display();
       }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    package com.qxcto;

/**
 * @author xuexuezi
 * @data 2022-7-25
 * @file 不带头结点的单链表的类定义及方法
 */
public class MySingleLinkedList {

    //链表定义头结点
    public ListNode head;

    //1.枚举法
    public void creatList(){
        ListNode now1 = new ListNode(1);
        ListNode now2 = new ListNode(2);
        ListNode now3 = new ListNode(3);
        ListNode now4 = new ListNode(4);

        this.head = now1;

        now1.next = now2;
        now2.next = now3;
        now3.next = now4;
    }
    //2.头插法
    public void addFirst(int data){
        ListNode newNode = new ListNode(data);
        newNode.next = this.head;//包含头指针为空的情况
        this.head = newNode;
    }
    //3.尾插法
    public void addLast(int data){
        ListNode newNode = new ListNode(data);
        ListNode cur = this.head;
        //处理空指针
        if(cur == null){
            this.head = newNode;
        }
        else{
            while(cur.next != null){
                cur = cur.next;
            }
            cur.next = newNode;
        }
    }
    //4.打印链表
    public void display(){
        ListNode cur = this.head;
        while(cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }
    //5.查找key在链表中的存在个数
    public int contains(int key){
        ListNode cur = this.head;
        int count = 0;
        while(cur != null){
            if(cur.val == key){
                count++;
            }
            cur = cur.next;
        }
        return count;
    }

    //6.返回链表长度
    public int listSize(){
        ListNode cur  = this.head;
        int Size = 0;

        while(cur != null){
            Size++;
            cur = cur.next;
        }
        return Size;
    }

    //7.1找到key值的前一个结点,key在首位或不存在返回null
    public ListNode searchKey(int key){
        if(this.head == null){
            return null;
        }

        ListNode cur = this.head;
        if(cur.val == key){
            return null;//头结点为key找不到头结点的前一个节点
        }

        while(cur.next != null){
            if(cur.next.val == key) {
                return cur;
            }else{
                cur = cur.next;
            }
        }
        return null;//如果找不到则是越界为null
    }

    //7.2找到索引index的前一个节点，链表中首个数据节点下标为0，索引为0或超出链表长度范围返回null
    public ListNode searchIndex(int index) {
        if(this.head == null){
            return null;
        }

        ListNode cur = this.head;
        int i = 1;//cur指向头结点，下标0。索引i指向cur的后一个节点与index比较
        if(index <= 0 || index > listSize()){
            return null;
        }
        while(i < index){
            cur = cur.next;
            i++;
        }
        return cur;//一定不为null可以找到
    }

    //8.任意位置插入节点，第一个数据节点默认下标0
    public boolean addIndex(int index, int data){
        if(this.head == null && index != 0){//空链表没有结点，只有index为0时才可以插入，相当于头插
            return false;
        }

        ListNode cur = this.head;//寻找要插入的位置的前一个结点
        ListNode newNode = new ListNode(data);

        if(index == 0){
            //头插属于特殊情况，中间插入要得到插入位置的前一个结点。
            newNode.next = this.head;
            this.head = newNode;
            return true;
        }

        //寻找要index位置的前一个节点
        cur = searchIndex(index);
        //此时cur正在要插入节点位置的前一位
        if(cur != null){
            newNode.next = cur.next;
            cur.next = newNode;
            return true;
        }
        return false;
    }

   //9.删除第一次出现关键字为key的节点
    public boolean remove(int key){//删除成功返回真,没有可删除的则返回假
        if(this.head == null){
            return false;
        }
        ListNode cur = this.head;
        //删除头结点的特殊情况
        if(cur.val == key){
            this.head = cur.next;
            return true;
        }

        //找key的前一个结点
        cur = searchKey(key);
        if(cur != null){
            cur.next = cur.next.next;
            return true;
        }
        return false;//链表里没有key

    }
    //10.删除所有值为key的节点：
    public boolean removeAllKey(int key){
        if(this.head == null){
            return false;
        }
        ListNode cur = this.head;
        boolean flag = false;
        //头结点为key
        while(cur.val == key){
            this.head = head.next;
            cur = this.head;
            flag = true;
        }
        //cur走到了新的头，并且不为key
        while(cur.next != null){
            if(cur.next.val == key){
                cur.next = cur.next.next;
                flag = true;
            }else{
                cur = cur.next;
            }
        }
        return flag;
    }
    //11.更改链表中第index个结点的值为data（首个数据节点下标默认0）
    public boolean changeIndex(int index, int data){
        if(this.head == null){
            return false;
        }
        if(index < 0 || index >= listSize()){//不能更改不存在的结点
            return false;
        }

        ListNode cur = this.head;
        int i = 0;//更改index位置，所以i与cur同步
        while(cur != null){
            if(i == index){
                cur.val = data;
                return true;
            }
            cur = cur.next;
            i++;
        }
        return false;//不可能走到这一步，因为不符合的情况开头已经排除
    }
    //12.更改链表中第一个key值为data
    public boolean changeKey(int key, int data){
        ListNode cur = this.head;
        while(cur != null){
            if(cur.val == key){
                cur.val = data;
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    //13.更改链表中所有key为data
    public boolean changeAllKey(int key, int data){
        ListNode cur = this.head;
        boolean flag = false;
        while(cur != null){
            if(cur.val == key){
                cur.val = data;
                flag = true;
            }
            cur = cur.next;
        }
        return flag;
    }
    //14.清空链表：每一个结点都置空
    public void clear(){
        ListNode cur = this.head;
        while(this.head != null){
            cur = head.next;
            this.head = null;
            this.head = cur;
        }
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    package com.qxcto;
/**
 * @file 带头结点的单链表类
 */
public class MyHeadSingleLinkedList {
    ListNode head = new ListNode();
    //1.枚举法
    public void creatList(){
        ListNode now1 = new ListNode(6);
        ListNode now2 = new ListNode(7);
        ListNode now3 = new ListNode(8);
        ListNode now4 = new ListNode(9);

        this.head.next = now1;

        now1.next = now2;
        now2.next = now3;
        now3.next = now4;

    }
    //2.头插法
    public void addFirst(int data){
        ListNode newNode = new ListNode(data);
        newNode.next = head.next;
        head.next = newNode;
    }
    //3.尾插法
    public void addLast(int data){
        ListNode newNode = new ListNode(data);
        //此时head一定不为空指针，因为带头结点的head是无参构造
        ListNode cur = head;
        while(cur.next != null){
            cur = cur.next;
        }
        cur.next = newNode;
    }
    //4.打印链表
    public void display(){
        ListNode cur = this.head.next;
        while(cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    //5.查找key存在个数
    public int contains(int key){
        ListNode cur = this.head.next;
        int count = 0;
        while(cur != null){
            if(cur.val == key){
                count++;
            }
            cur = cur.next;
        }
        return count;
    }
    //6.返回链表长度
    public int listSize(){
        ListNode cur = this.head.next;
        int Size = 0;

        while(cur != null){
            Size++;
            cur = cur.next;
        }
        return Size;
    }

    //7.1找到第一次出现的key值的前一节点,没有key存在则返回null
    public ListNode searchKey(int key) {
        ListNode cur = this.head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                return cur;
            } else {
                cur = cur.next;
            }
        }
        return null;
    }
    //7.2找到索引index的前一个节点，链表中首个数据节点下标为0，索引超出链表长度范围返回null
    public ListNode searchIndex(int index) {
        if(this.head.next == null && index != 0){
            return null;
        }

        int i = 0;
        ListNode cur = this.head;//为i所指的前一个结点
        if(index < 0 || index > listSize()) {
            return null;
        }

        while(i < index) {
            cur = cur.next;
            i++;
        }
        return cur;
    }

    //8.任意位置插入节点，第一个数据节点默认下标0
    public boolean addIndex(int index, int data){

        ListNode newNode = new ListNode(data);
        ListNode cur = searchIndex(index);

        if(cur != null) {
            newNode.next = cur.next;
            cur.next = newNode;
            return true;
        }
        return false;
    }

    //9.删除第一次出现关键字为key的节点：
    public boolean remove(int key){
        ListNode cur = this.head;
        cur = searchKey(key);

        if(cur != null){
            cur.next = cur.next.next;
            return true;
        }
        return false;
    }
    //10.删除所有值为key的节点：
    public boolean removeAllKey(int key){
        ListNode cur = this.head;
        boolean flag = false;
        while(cur.next != null){
            if(cur.next.val == key){
                cur.next = cur.next.next;//删了一位挪上来的下一位不确定是不是还是key，所以继续走循环检查
                flag = true;
            }else{
                cur = cur.next;//只有下一项不用删才走动。
            }
        }
        return flag;
    }
    //11.更改链表中第index个结点的值为data（首个数据节点下标默认0）
    public boolean changeIndex(int index, int data){
        if(index < 0 || index >= listSize()){
            return false;
        }

        int i = 0;//i与cur保持在同一个结点
        ListNode cur = this.head.next;

        while(cur != null){
            if(i == index){
                cur.val = data;
                return true;
            }else{
                cur = cur.next;
                i++;
            }
        }

        return false;
    }
    //12.更改链表中第一个key值为data
    public boolean changeKey(int key, int data){
        ListNode cur = head.next;
        while(cur != null){
            if(cur.val == key){
                cur.val = data;
                return true;
            }else{
                cur = cur.next;
            }
        }

        return false;
    }
    //13.更改链表中所有key为data
    public boolean changeAllKey(int key, int data){
        ListNode cur = head.next;
        boolean flag = false;
        while(cur != null){
            if(cur.val == key){
                cur.val = data;
                flag = true;
            }
            cur = cur.next;
        }

        return flag;
    }
    //14.清空链表：
    public void clear(){
        ListNode cur = head.next;
        while(head.next != null){
            cur = head.next;
            this.head = null;
            this.head = cur;
        }
    }

}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201

    63.203移除链表元素-3种写法（含递归）

    203.移除链表元素
    在这里插入图片描述
    在这里插入图片描述
    思路： 此处默认应指的是不带头结点的单链表
    1>我的方法
    分为两种情况，key在头指针和key不在头指针,两个while循环分别进行头删，和中间删除
    2>官方的递归
    在这里插入图片描述在这里插入图片描述当head为空时结束递归，先递归调用自身判断head.next删除val后的结点
    再判断head指向的自身是否为val,如果是将head.next返回给自己的前一个结点，即删除。如果不等于val,返回自身给上一个结点调用的head.next

    3>官方的迭代
    设置一个虚拟头结点再进行删除操作。
    在这里插入图片描述

    63.203 代码实现

    方法一： key在头与不在头区分开
    在这里插入图片描述

    /**
 * 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) {
        ListNode cur = head;
        //判断头
        while(head != null){
            if(head.val == val){
                head = head.next;
            }else{
                break;
            }
        }
        cur = head;
        //此时cur在不为val的头结点，或头删完了，cur为null
        while(cur != null && cur.next != null){
            if(cur.next.val == val){
                cur.next = cur.next.next;
            }else{
                cur = cur.next;
            }
        }
        return head;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    方法二： 递归
    在这里插入图片描述

    class Solution {
    public ListNode removeElements(ListNode head, int val) {
       if(head == null){
           return null;
       }
       head.next = removeElements(head.next,val);
       return head.val == val?head.next:head;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    方法三： 设置虚拟头结点，也称哨兵结点dummyHead
    在这里插入图片描述

    
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //设置dummyHead作为头结点
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        ListNode cur = dummyHead;
        while(cur.next != null){
            if(cur.next.val == val){
                cur.next = cur.next.next;
            }else{
                cur = cur.next;
            }
        }

        return dummyHead.next;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    ★64.707设计链表-3种写法

    707.设计链表
    在这里插入图片描述在这里插入图片描述
    思路：
    1>我的，带头结点的单链表,没定义ListNode
    自己多写一个方法listSize()来返回链表长度，头插尾插都用原始写法，用while循环
    2>官方，带头结点的单链表
    头插尾插调用index任意位置插入的方法，并对链表属性size进行值变化，用for循环
    遇到问题：ListNode的定义无法像题解那样被识别，需要重新定义
    在这里插入图片描述

    在这里插入图片描述

    3>官方双链表
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    重点理解： index+1为index结点前的结点数包含head，size-index表示index后的结点数包含tail。都不包括index
    无需考虑的太复杂，直接画一个简单链表对比边界条件如何定义即可
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述

    64.707 代码实现

    方法一： 带头结点的单链表，多写了一个listSize()返回链表长度。虽然在链表中定义了头结点和链表长度，但并没有对size赋值，且头插尾插都用的普通写法和while循环
    在这里插入图片描述

    class MyLinkedList {

    int size;
    ListNode head;
    public MyLinkedList() {
        size = 0;
        head = new ListNode();//带头结点
    }
    public int listSize(){
        ListNode cur = head.next;
        int count = 0;
        while(cur != null){
            cur = cur.next;
            count++;
        }
        return count;
    }
    public int get(int index) {
        if(index < 0 || index >= listSize()){
            return -1;
        }
        int i = 0;
        ListNode cur = head.next;
        while(i < index){
            cur = cur.next;
            i++;
        }
        return cur.val;
    }
    
    public void addAtHead(int val) {
        ListNode newNode = new ListNode(val);
        newNode.next = head.next;
        head.next = newNode;
    }
    
    public void addAtTail(int val) {
        ListNode newNode = new ListNode(val);
        ListNode cur = head;
        while(cur.next != null){
            cur = cur.next;
        }
        cur.next = newNode;
    }
    
    public void addAtIndex(int index, int val) {
         if(index > listSize()){
            return;
        }

        ListNode cur = head;//保持在i的前驱结点
        int i = 0;
        ListNode newNode = new ListNode(val);
        //因为带头结点，所以统一处理
        if(index <= 0){
            newNode.next = head.next;
            head.next = newNode;
        }
        else{
            while(i < index){
                cur = cur.next;
                i++;
            }
            newNode.next = cur.next;
            cur.next = newNode;
        }
    }
    
    public void deleteAtIndex(int index) {
         if(index >= listSize() || index < 0){
            return;
        }
        int i = 0;
        ListNode cur = head;
        while(i < index){
            cur = cur.next;
            i++;
        }

        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);
 */


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93

    方法二： 完善单链表写法
    在这里插入图片描述

    public class ListNode {
    int val;
    ListNode next;
    ListNode(){
        this.next = null;
    }
    ListNode(int x){
        val = x;
        this.next = null;
    }
    ListNode(int x,ListNode next){
        val = x;
        this.next = next;
    }
}
class MyLinkedList {

    ListNode head;
    int size;
    public MyLinkedList() {
        size = 0;
        head = new ListNode();
    }
    
    public int get(int index) {
         if (index < 0 || index >= size) {//索引有效值[0,size-1]
            return -1;//同时处理了空链表情况
        }

        ListNode cur = head.next;//第一个数据节点下标0
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        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;
        }
        if (index < 0) {
            index = 0;
        }

        ListNode pred = head;//指向头结点，保持在索引结点的前驱结点上
        for (int i = 0; i < index; i++) {
            pred = pred.next;
        }
        //此时cur的后继就是要插入的新结点位置
        ListNode newNode = new ListNode(val);
        newNode.next = pred.next;
        pred.next = newNode;
        ++size;
    }
    
    public void deleteAtIndex(int index) {
         if((index<0) || (index>=size)){
            return;
        }

        ListNode pred = head;//pred是索引结点的前驱
        for(int i=0; i<index; i++){
            pred = pred.next;
        }
        pred.next = pred.next.next;
        --size;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76

    方法三： 双链表，两头带，头结点head和尾结点tail
    奇怪的报错：找到了，真正的错误不在报错位置，在上一个函数

    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    public class ListNode {
    int val;
    ListNode prev;
    ListNode next;
    ListNode(){
        this.next = null;
        this.prev = null;
    }
    ListNode(int x){
        val = x;
        this.next = null;
        this.prev = null;
    }
}
class MyLinkedList {
    ListNode head;
    ListNode tail;
    int size;
    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
        tail = new ListNode(0);
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int index) {
         if (index < 0 || index >= size) {//索引有效值[0,size-1]
            return -1;//同时处理了空链表情况
        }
        ListNode cur;
        if(index+1 < size-index){
            cur = head;
            for(int i=0; i<index+1; i++){
                cur = cur.next;
            }
        }else{
            cur = tail;
            for(int i=0; i<size-index; i++){
                cur = cur.prev;
            }
        }
        return cur.val;
    }
    
    public void addAtHead(int val) {
       ListNode newNode =new ListNode(val);
       newNode.next = head.next;
       head.next.prev = newNode;
       head.next = newNode;
       newNode.prev = head;
       ++size;
    }

    public void addAtTail(int val) {
       ListNode newNode = new ListNode(val);
       newNode.next = tail;
       tail.prev.next = newNode;
       newNode.prev = tail.prev;
       tail.prev = newNode;
       ++size;
    }
    
    public void addAtIndex(int index, int val) {
       //需要找到插入位置的前驱和后继
        if(index > size){
            return;
        }
        if(index < 0){
            index = 0;
        }
        ListNode newNode = new ListNode(val);
        ListNode pre = head;
        ListNode succ = tail;
        if(index < size-index){//index距离尾大于距离头
            for(int i=0; i<index; i++){//从head，i=0开始，i=index时prev为index结点的前驱
                pre = pre.next;
            }
            succ = pre.next;
        }else{
            for(int i=0; i<size-index; i++){
                succ = succ.prev;
            }
            pre = succ.prev;
        }
        newNode.next = succ;
        newNode.prev = pre;
        pre.next = newNode;
        succ.prev = newNode;
        ++size;
    }
    
    public void deleteAtIndex(int index) {
         if((index<0) || (index>=size)){
            return;
        }
        ListNode pred = head;
        ListNode succ = tail;
       if(index < size-index){
           for(int i=0; i<index; i++){
               pred = pred.next;
           }
           succ = pred.next.next;
       }else{
           for(int i=0; i<size-index-1; i++){
               succ = succ.prev;
           }
           pred = succ.prev.prev;
       }

       pred.next = succ;
       succ.prev = pred;
        --size;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115

    ★65.206反转链表-2种写法（含递归）

    206.反转链表
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    思路：
    1>双指针法
    考虑用两个指针将两个相邻结点的链反转，注意需要再用一个指针保存之后的结点，免得反转后找不到
    在这里插入图片描述

    2>递归
    在这里插入图片描述

    65.206代码实现

    方法一：双指针
    在这里插入图片描述

    /**
 * 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) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode temp;
        while(cur != null){
            temp = cur.next;
            cur.next = pre;
            
            pre = cur;
            cur = temp;

        }
        return pre;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    方法二： 递归
    在这里插入图片描述

    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;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    ★66.24两两交换链表中的结点-2种写法（含递归）

    24.两两交换链表中的结点
    在这里插入图片描述
    在这里插入图片描述
    思路：
    1>双指针迭代
    定义一组双指针，指向要交换的两个相邻元素，多定义一个temp指针用来保存要交换的结点的后续结点，以免改变结点指向后找不到后续结点的头。定义一个前驱指针pre，用来连接交换的两个结点的前驱
    考虑空链表，考虑单数个结点的情况，后续单数个结点不用交换
    在这里插入图片描述

    2>递归

    每次先交换自己在的head和head.next。然后调用自身函数指向这两个结点的后继

    66.24代码实现

    方法一：双指针
    四个指针
    在这里插入图片描述

    /**
 * 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 swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        ListNode pre = dummyHead;
        ListNode t1 = pre.next;
        ListNode t2 = t1;
        ListNode temp = t1;
        while(t1 != null && t1.next !=null){
            t2 = t1.next;
            temp = t2.next;

            //进行交换
            pre.next = t2;
            t2.next = t1;
            t1.next = temp;

            pre = t1;
            t1 = temp;
        }
        return dummyHead.next;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    方法二：递归
    在这里插入图片描述

    class Solution {
    public ListNode swapPairs(ListNode head) {
       if(head == null || head.next == null){
            return head;
        }
        ListNode t2 = head.next;
        head.next = swapPairs(t2.next);
        t2.next = head;

        return t2;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    ★★67.19 删除链表的倒数第N个结点-3种写法（3.用栈）

    19.删除链表的倒数第N个结点
    在这里插入图片描述
    在这里插入图片描述
    思路：
    1>双指针
    定义一对指针，快指针到达null的时候，慢指针正好在要删除的结点的前驱结点上。两指针的相隔距离由形参n决定，n=1时，快指针先走一步，然后快慢指针再一起走。n=2时，快指针先走两步，然后再一起走
    因为要删除所以定义了伪头结点dummyHead
    在这里插入图片描述

    2>先遍历一次计算链表长度
    第二次遍历停在第listSize-n个结点上，删除后继结点
    ★3>官方方法二，栈
    用到的栈操作
    菜鸟教程java中栈的操作
    普通构造栈Stack st = new Stack();
    使用LinkedList的Deque接口把队列当栈用Deque stack = new LinkedList();
    双端队列使用详解

    入栈 stack.push(cur);
    出栈 stack.pop();
    取栈顶元素 stack.peek();
    在这里插入图片描述
    在这里插入图片描述

    67.19代码实现

    方法一： 快慢指针
    在这里插入图片描述
    不带头结点

    
/**
 * 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 removeNthFromEnd(ListNode head, int n) {
        ListNode tail = head;
        ListNode deletePre = head;
        int i = 0;
        for(i=0; i<n; i++){
            if(tail != null){
                tail = tail.next;
            }else{
                break;//n越界
            }
        }
        //排除n=size，要删除的是头结点没有前驱的情况
        if(tail == null){
            head = head.next;
            return head;
        }
        //普通情况
        while(tail.next != null){
            tail = tail.next;
            deletePre = deletePre.next;
        }
        deletePre.next = deletePre.next.next;
        return head;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    带头结点
    在这里插入图片描述

    
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        ListNode tail = dummyHead;//快指针走到最后一个数据结点停止
        ListNode deletePre = dummyHead;//慢指针走到要删除的前驱结点

        for(int i=0; i<n; i++){
            tail = tail.next;
        }
        while(tail.next != null){
            tail = tail.next;
            deletePre = deletePre.next;
        }
        if(head != null){
            deletePre.next = deletePre.next.next;
        }
        return dummyHead.next;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    方法二： 遍历两遍
    在这里插入图片描述
    不带头结点

    //不带头结点
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
          ListNode cur = head;
        int size = 0;
        while(cur != null){
            cur = cur.next;
            size++;
        }
        if(size == n){
            head = head.next;
            return head;
        }
        cur = head;
        for(int i=0; i<size-n-1; i++){
            cur = cur.next;
        }
        cur.next = cur.next.next;
        return head;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    带头结点
    在这里插入图片描述

    class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;

        ListNode cur = dummyHead.next;
        int size = 0;
        while(cur != null){
            cur = cur.next;
            size++;
        }

        cur = dummyHead;
        for(int i=0; i<size-n; i++){
            cur = cur.next;
        }
        if(head != null){
            cur.next = cur.next.next;
        }
        return dummyHead.next;
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    方法三： 调用栈

    在这里插入图片描述

    class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
      ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        Deque<ListNode> stack = new LinkedList<ListNode>();
        ListNode cur = dummyHead;
        while(cur != null){
            stack.push(cur);
            cur = cur.next;
        }
        
        for(int i=0; i<n; i++){
            stack.pop();
        }
        
        ListNode pre = stack.peek();
        pre.next = pre.next.next;
        
        return dummyHead.next;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    ★68.面试题02.07链表相交-3种写法（2.官方双指针3.哈希）

    面试题02.07链表相交
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    思路：
    1>我的双指针，从两个结点的末尾开始从后往前比较
    把两个结点都遍历到末尾，计算A，B链表的长度，较长的链表第二次遍历时先走多出的几步，如示例1中B先走一步，再进行A，B结点的比较，同步走并依次比较，遇到相同结点则返回。

    ★2>官方的双指针，大为震撼，屠龙之技
    简单理解为：
    链表A，B长度不同的情况下，A，B指针都走过一遍链表A和链表B的不相交长度+相交长度。就会同时走到相交点，该结点也是两指针第一次同时指向的结点。
    链表A，B长度相同的情况下，同步走会遇到相交点
    若不相交，指针A,B走完两个链表长度时会同时在对方链表上结束，指向null。
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    3>官方的哈希集合

    68.面试02.07代码实现

    方法一： 我的双指针，从末尾判断两链表长度差，然后保持后序结点数相同再同步走动
    在这里插入图片描述

    /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       int sizeA = 0;
        int sizeB = 0;
        ListNode curA = headA;
        ListNode curB = headB;
        while(curA != null){
            curA = curA.next;
            sizeA++;
        }
        while(curB != null){
            curB = curB.next;
            sizeB++;
        }
        curA = headA;
        curB = headB;
        if(sizeA >= sizeB){
            for(int i=0; i<sizeA-sizeB; i++){
                curA = curA.next;
            }
        }else{
            for(int i=0; i<sizeB-sizeA; i++){
                curB = curB.next;
            }
        }

        while(curA !=null && curB != null){//按理说此处写一个就行
            if(curA == curB){
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;//不相交
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48

    方法二：官方的双指针两个指针走到null后去走对方的链表，链表A长a链表B长b，两个指针都走遍a+b后必然相遇在相交点
    在这里插入图片描述

    public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
      if(headA == null || headB == null){
            return null;
        }
        ListNode pA = headA;
        ListNode pB = headB;
        while(pA != null || pB != null){
            if(pA == null){
                pA = headB;
            }
            if(pB == null){
                pB = headA;
            }
            if(pA == pB){
                break;
            }
            

            pA = pA.next;
            pB = pB.next;
        }
        return pA;//返回相交结点，或都走到了null
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    方法三：哈希集合

    ★69.142.环形链表2-3种写法（2.官方双指针3.哈希）

    142.环形链表2
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    思路：
    1>我的快慢指针指针，比较普适
    ①考虑怎么找到环的入口，定义快慢指针，fast每次走两步，slow每次走一步，一定会在环内相遇。
    为啥slow走一步，fast走两步，有环的话一定相遇呢？
    因为fast每次都比slow多走一步，按相对位移来说，在环内，fast从slow的后面一次一步追赶slow，所以fast和slow一定会相遇。
    ②第一次相遇后，fast变为一次走一步，并记录步数，slow停在原地，直到fast再次与slow相遇，此时的步数即为环内结点数。
    ③如环内结点数为n,让fast比slow先走n-1步，这种情况下， 如果slow停在环入口，则fast一定在环尾，并且fast.next == slow 。 按照这种思路，fast.next如果不与slow相等，说明slow没有走到环头，fast和slow同步走，记录步数，slow走到环头时，步数即为当前结点的索引

    ★2>官方的快慢指针，屠龙之技
    在这里插入图片描述
    在这里插入图片描述

    a+(n+1)b+nc = 2(a+b)
a = nb-b+nc
a = nc-c + nb-b +c
a = (n-1)(b+c) +c

    • 1
    • 2
    • 3
    • 4

    此时计算的所有数据a,b,c都是，有环情况下，fast与slow相遇时走过的路程，尤其c的含义，特指从快慢指针相遇点往后走到环入口的距离
    a为入环前结点数，b+c为环内结点数，c为相遇点到入环点的结点数。
    得到：从相遇点到入环的距离+（n-1)圈的环长=从链表头到入环点的距离）
    因此，当发现 slow 与fast 相遇时，我们再额外使用一个指针ptr。起始，它指向链表头部；随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇。
    中间slow会走过n-1圈
    3>哈希表

    69.142代码实现

    方法一：我的双指针，分三步
    在这里插入图片描述

    /**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        int pos =  0;
        ListNode slow = head;
        ListNode fast = head;

        while(slow != null && fast != null){//1.判断是否有环，fast一次走2，slow一次走1
            if(fast.next == null){
                pos = -1;
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                break;//第一次相遇，改变走法
            }
        }
        if(slow == null || fast == null){
            pos = -1;
            return null;//无环或空链表
        }

        //2.有环，且fast和slow此时停在同一个结点
        int ringNum = 1;//记录环内结点数
        fast = fast.next;//使slow和fast再次相遇，slow不动，fast一次走1
        while(slow != fast){
            fast = fast.next;
            ringNum++;
        }

        //3.得到ringNum为环内结点数，fast先走ringNum-1步
        fast = head;
        slow = head;
        for(int i=0; i<ringNum-1; i++){
            fast = fast.next;
        }
        while(fast.next != slow){//当fast.next==slow时，slow在环入口
            slow = slow.next;
            fast = fast.next;
            pos++;
        }
        return slow;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55

    方法二：官方双指针思路 fast,slow相遇后，再走到环入口，恰好与头走到环入口相遇
    在这里插入图片描述

    /**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = 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;//无环
        }

        ListNode ptr = head;
        while(ptr != slow){
            ptr = ptr.next;
            slow = slow.next;
        }
        return ptr;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38

    官方写法

    public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            if (fast == slow) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    方法三：哈希

  • 相关阅读:
    vmware安装centos7并制作多副本
    重温数据结构与算法之前缀和
    MySQL--对于库的操作&&对于表的操作
    世界数字工厂的发展现状究竟如何？仅10%公司实施完成！
    Ubuntu 设置sudo免密NOPASSWD
    设计模式之模板方法模式C++实现
    力扣：72. 编辑距离
    从头训练RNN语言模型，这样的loss正常吗？
    基于simulink的模糊自整定PID控制器设计与仿真
    C/C++算法入门 | 图形输出
  • 原文地址：https://blog.csdn.net/qq_24990383/article/details/125901921