代码随想录算法训练营第三天 链表 cb2bbb29ee284b02af90933ba9e20fdb

代码随想录算法训练营第三天|?链表

链表理论基础

203.溢出链表元素

707.设计链表

206.反转链表

1.了解链表理论基础

https://programmercarl.com/链表理论基础.html#链表的类型

2.LeetCode 203.移出链表元素

题目链接：https://leetcode.cn/problems/design-linked-list/submissions/

2.1自己看到题目的第一想法

思路：分不清虚拟头节点和头节点

2.2看完代码随想录之后的想法

    //1.这里我们所说的head不是指一个不放数据，指针指向第一个有data的节点
    //这里的head指的是头指针指向链表的第一个节点（不是不妨数据那一个）

    //而我们潜意识以为的一个不放数据，指针指向第一个有data的节点是虚拟头节点

思路1：不用虚拟头节点

代码1：

/**
 * 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) {
        //看实例
        //：head = [1,2,6,3,4,5,6]
        //当val等于头节点时，要删除的就是头节点第一个节点，但是我们直到单链表的删除，需要找到被删除的前一个节点。而头节点前面已经没有节点了，怎么进行删除呢
        //很简单，就是让头节点指向头节点的下一个节点就行，这样头节点就变成了下一个节点
        //然后删除后，继续移动指针，看看下一个是否跟目标值相等
        
        //head!=null,确保有指向的下一个，不是空指针
        //删除头节点的情况
        while(head!=null&&head.val==val){
                head=head.next;
        }
        //2.这里为什么要用另外一个节点来遍历，而不是用head,而且返回head还是用另外一个节点遍历之后的结果
        //这是因为ListNode curNode=head;head和curnode指向的是同一个地址，curnode改变，head整个链表也会跟着改变。
        //而我们不使用head是因为，拿head去遍历，那么head会指向链表最后一个元素，这样我们就不知道整个链表中除了等于val以外的所有元素。
        //我们创建的链表副本curcode作用是为了保证不改变默认的头节点的指向，且head和curnode之间是若引用的关系，所以改变副本链表中的某个指针的指向也会同步在head上

        //不用删除头节点的情况,那么新的头节点还是head,不用发生变化
        //那么我们需要重新定义个新的节点，用来遍历每一个节点
        ListNode curNode=head;
        while(curNode!=null&&curNode.next!=null){
            //3.为什么curNode.next!=null
            //因为这样子会 遍历到整个链表的倒数第二位，然后在下面的if中.next会找到最后一位节点，这样子整个链表就都遍历完了
            if(curNode.next.val==val){
                //相当于头节点的下一个节点值等于目标值
                //那么要删除的就是将头节点的指针指向
                curNode.next=curNode.next.next;
            }else{
                //如果没有等于目标值
                //那么就让当前指针指向下一位
                curNode=curNode.next;
            }
        }
        return head;

        //1.这里我们所说的head不是指一个不放数据，指针指向第一个有data的节点
        //这里的head指的是头指针指向链表的第一个节点（不是不妨数据那一个）

        //而我们潜意识以为的一个不放数据，指针指向第一个有data的节点是虚拟头节点
    }
}

思路2：用虚拟头节点

代码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) {

        //第二种方法，用虚拟头节点
        //定义一个虚拟的头节点，没有数据，指针指向第一个节点
        //那么现在就不存在头节点为空的情况了
        ListNode xhead=new ListNode();
        xhead.next=head;
        //同样不使用虚拟头节点来进行遍历（这样会改变了head的值）//使用另外的指针来遍历
        ListNode curNode=xhead;
        while(curNode.next!=null){
            //遍历下去
            if(curNode.next.val==val){
                curNode.next=curNode.next.next;
            }else{
                curNode=curNode.next;
            }
        }
        return xhead.next;
    }
}

3.LeetCode 707.设计链表

题目链接：https://leetcode.cn/problems/design-linked-list/submissions/

3.1自己看到题目的第一想法

思路：到底哪一个是头节点啊，到底哪一个是下标的开始啊，懵圈圈

3.2看完代码随想录之后的想法

    //虚拟头节点没有下标
    //虚拟头节点的指针指向的第一个有data的节点下标才是0

while(curNode.next!=null){
curNode=curNode.next;
//极端判断
//当下标为0的这个节点是最后一位节点时，此时的
//curNode是dumyhead;
//下标为0的节点为cueNode.next
//要被操作的节点是curNode.next,前一个是curNode,那么这就对了
}
//找到了那个节点

代码：

//定义节点
class Node{
    int val;
    Node next;
    public Node(){};
    public Node(int val){
        this.val=val;
    }
}

//链表
class MyLinkedList {
    //使用虚拟头节点实现
    Node dumyhead;
    //定义里面含有data的size
    int size;
    
    public MyLinkedList(){
        //初始化链表
        size=0;
        dumyhead=new Node(0);
    }
    
    public int get(int index) {
        //首先要明白这个链表中下标是怎么算的
        //已知下标从0开始

        //虚拟头节点没有下标
        //虚拟头节点的指针指向的第一个有data的节点下标才是0
        //才算开始

        //首先先判断index是否合法，要在第一个有data的节点下到链表中的最大size
        if(index<0||index>size-1){
            return -1;
        }
        //在[0,size-1]的情况
        //那么我们要找到下标为index的节点

        //创建一个新指针用来遍历链表，不用虚拟头节点，因为那样会把它头节点的位置该变量
        Node curNode=dumyhead;
        //那么下标为0的节点就是 curNode.next
        while(index>0){
            //让index来控制要循环多少次
            curNode=curNode.next;
            //如何判断是否真的能够找到那个下标为index的节点呢
            //我们做极端假设，假设，我们的index是0，
            //那么此时不满足while循环条件，不会执行里面的语句，那么此时的curNode就是dumyNode,
            //下标为0的节点就是curNode.next
            index--;
        }
        return curNode.next.val;
    }
    
    public void addAtHead(int val) {
      //将一个值为 val 的节点插入到链表中第一个元素之前
      //就是在链表头部添加节点
      //首先要创建出来这个新节点，往虚拟头节点后放，让他成为第一个有data的节点
      Node newNode=new Node(val);

      //创建新指针
      Node curNode=dumyhead;
      //用新指针来遍历,此时新指针指向虚拟节点处
      newNode.next=curNode.next;
      curNode.next=newNode;
      size++;
    }
    
    public void addAtTail(int val) {
        // 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
        //就是在链表尾部添加节点
        //首先也是先创建这个要添加的新的节点
        Node newNode=new Node(val);
        //要找到最后一个节点，也就是指针指向null的那个节点

        //创建新指针
        Node curNode=dumyhead;
        while(curNode.next!=null){
            curNode=curNode.next;
            //极端判断
            //当下标为0的这个节点是最后一位节点时，此时的
            //curNode是dumyhead;
            //下标为0的节点为cueNode.next
            //要被操作的节点是curNode.next,前一个是curNode,那么这就对了
        }
        //找到了那个节点
        curNode.next=newNode;
        size++;
    }
    
    public void addAtIndex(int index, int val) {
        //判断边界
        if(index>size){
            return;//直接退出
        }
        if(index<0){
            index=0;
        }
        //将一个值为 val 的节点插入到链表中下标为 index 的节点之前
        //把新节点添加在指定的位置下标处

        //创建新节点
        Node newNode=new Node(val);
        //创建新遍历的指针
        Node curNode=dumyhead;
        //寻找指定下标的前一个节点
        while(index>0){
            //作为循环次数
            curNode=curNode.next;
            index--;
            //极端判断，加入index为0，那么此时curNode=dumyhead,下标为0的位置就是curNode.next;
        }
        //当前节点就是要添加的前一位
        newNode.next=curNode.next;
        curNode.next=newNode;
        size++;
    }
    
    public void deleteAtIndex(int index) {
       //如果下标有效，则删除链表中下标为 index 的节点。
       //删除指定位置的节点、
    
       //先创建遍历的新指针
       Node curNode=dumyhead;
       //首先要判断是否合法
       if(index>=0&&index<size){
           //找到index位置处的节点的前一个位置
           while(index>0){
               //作为循环条件的判断
               curNode=curNode.next;
               index--;
           }
           curNode.next=curNode.next.next;
           size--;
       }
    }
}

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

4.LeetCode 206.反转链表

题目链接：https://leetcode.cn/problems/reverse-linked-list/submissions/

4.1自己看到题目的第一想法

思路：双指针

4.2看完代码随想录之后

代码1（双指针法，curNode,prev,还有一个临时的指针temp)

/**
 * 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) {
        //一个一个节点进行往下反转
        //用双指针来解决，首先先定义一个指针用来遍历来链表的，我们定做curNode
        //接着我们定义另外一个指针，用来记录反转之后的指针
        ListNode curNode=head;
        ListNode prev=null;
        //然后每次把curNode下一个的节点记录下来。
        //把curNode的指针指向prev

        //然后把prev移动到curNode的位置，curBode移动到保留的之前的那个位置
        //移动直到prev的下一个节点为空时
        //即反转成功
        ListNode temp=null;
        while(curNode!=null){
            //不为空才会往下去遍历
            temp=curNode.next;
            curNode.next=prev;

            //移动指针
            prev=curNode;
            curNode=temp;
        }
        //到最后prev就是头节点了
        return prev;
    }
}

代码2（递归法，不熟悉，容易绕晕，需要先清楚双指针，熟悉双指针）

class Solution {
    public ListNode reverseList(ListNode head) {
        //递归法
        //对双指针很熟练之后再写递归
        //ListNode result=reverse(head,null);
        return reverse(head,null);

    }
    public ListNode reverse(ListNode curNode,ListNode prev){
        if(curNode==null){
            return prev;
        }
        ListNode temp=null;
        temp=curNode.next;
        curNode.next=prev;

        return reverse(temp,curNode);
    }
}

5.今日收获，记录一下自己的成长

今日收获了

1.学习了链表的基础知识

2.开始学习对链表的定义，操作（注意有无虚拟头节点，注意指针）

3.双指针在链表中应用也很广泛

4.刚接触递归，不过不熟，有点懵圈