代码随想录 day 3 第二章链表part01

第一题:203.移除链表元素

思路

设置虚拟头节点：创建一个虚拟头节点 dummy，并将 dummy.next 指向链表的头节点 head。这样可以简化对头节点的处理，避免在删除头节点时进行特殊判断。
初始化指针：使用一个指针 cur 指向虚拟头节点 dummy，从虚拟头节点开始遍历链表。
遍历链表：使用 while 循环遍历链表，直到 cur.next 为 null（即到达链表末尾）。在每次循环中，检查 cur.next 节点的值是否等于目标值 target：如果相等，跳过该节点，即将 cur.next 指向 cur.next.next。如果不相等，移动指针 cur 到下一个节点，即 cur = cur.next。
返回新的头节点：最后返回 dummy.next，即新的链表头节点。

代码：

class Solution {
    public ListNode removeElements(ListNode head, int target) {
        // 设置一个虚拟的头结点
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode cur = dummy;
        while (cur.next != null) {
            if (cur.next.val == target) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

第二题:707.设计链表

思路：

（1）节点类 ListNode

首先定义了节点类 ListNode，每个节点有两个成员变量：

int val：存储节点的值。
ListNode next：指向下一个节点的指针。

（2）链表类 MyLinkedList

①成员变量

int size：记录链表中实际元素的数量。
ListNode head：链表的虚拟头节点，用于简化边界条件的处理。

②构造函数

public MyLinkedList()：初始化链表对象，设置 size 为 0，并创建一个虚拟头节点 head。

③方法

获取节点值 get(int index)如果索引 index 无效（小于0或大于等于链表大小），则返回 -1。否则，从虚拟头节点开始遍历至第 index + 1 个节点（因为虚拟头节点不算作实际数据节点），并返回该节点的值。
在头部添加节点 addAtHead(int val)创建一个新节点 newNode，其值为 val。将新节点的 next 指向原头节点（即 head.next）。更新虚拟头节点的 next 指向新节点。增加链表大小 size。
在尾部添加节点 addAtTail(int val)创建一个新节点 newNode，其值为 val。从虚拟头节点开始遍历至链表的最后一个节点。将最后一个节点的 next 指向新节点。增加链表大小 size。
在指定位置插入节点 addAtIndex(int index, int val)如果索引 index 大于链表大小，则不执行任何操作。如果索引 index 小于0，则将其视为在头部插入。增加链表大小 size。找到要插入节点的前一个节点 pred。创建新节点 toAdd，并将其 next 指向 pred.next。更新 pred.next 指向新节点 toAdd。
删除指定位置的节点 deleteAtIndex(int index)如果索引 index 无效，则不执行任何操作。减少链表大小 size。找到要删除节点的前一个节点 pred。更新 pred.next 指向 pred.next.next，从而跳过要删除的节点。

代码

class ListNode{
    int val;
    ListNode next;
    ListNode(){}
    ListNode(int val){
        this.val = val;
    }
}
class MyLinkedList {
    int size;//存储链表元素的个数
    ListNode head;//虚拟头结点
    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
    }
    //获取第index个节点的数值，注意index是从0开始的，第0个节点就是头结点
    public int get(int index) {
        //如果index非法，返回-1
        if(index < 0 || index >= size){
            return -1;
        }
        ListNode currentNode = head;
        //包含一个虚拟头结点，所以查找第index + 1个节点
        for(int i = 0; i <= index; i++){
            currentNode = currentNode.next;
        }
        return currentNode.val;
    }
    
    public void addAtHead(int val) {
        ListNode newNode = new ListNode(val);
        newNode.next = head.next;
        head.next = newNode;
        size++;
        //在链表最前面插入一个节点，等价于在第0个元素前添加
        //addAtIndex(0,index)
    }
    
    public void addAtTail(int val) {
        ListNode newNode = new ListNode(val);
        ListNode cur = head;
        while(cur.next != null){
            cur = cur.next;
        }
        cur.next = newNode;
        size++;
        //在链表的最后插入一个节点，等价于在（末尾+1）个元素前添加
        //addAtIndex(size,val)
    }
    //在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头结点
    //如果index等于链表的长度，则说明新插入的节点为链表的尾节点
    //如果index大于等于链表的长度，则返回空
    public void addAtIndex(int index, int val) {
        if(index > size){
            return ;
        }
        if(index < 0){
            index = 0;
        }
        size++;
        //找到需要插入节点的前驱
        ListNode pred = head;
        for(int i = 0;i < index;i++){
            pred = pred.next;
        }
        ListNode toAdd = new ListNode(val);
        toAdd.next = pred.next;
        pred.next = toAdd;
    }
    //删除第index个节点
    public void deleteAtIndex(int index) {
        if(index < 0 || index >= size){
            return;
        }
        size--;
        //因为有虚拟头结点，所以不用对index=0的情况进行特殊处理
        ListNode pred = head;
        for(int i = 0;i < index; i++){
            pred = pred.next;
        }
        pred.next = pred.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);
 */

第三题:206.反转链表

思路一：双指针

初始化指针：prev 初始化为 null，表示反转后的链表的最后一个节点（初始时没有节点）。cur 初始化为 head，表示当前处理的节点，从链表的头节点开始。temp 初始化为 null，用于暂时保存当前节点的下一个节点。
遍历链表：使用 while 循环遍历链表，直到 cur 为 null（即到达链表末尾）。在每次循环中：用 temp 保存 cur.next，即当前节点的下一个节点，防止在修改 cur.next 时丢失链表的后续部分。将 cur.next 指向 prev，即将当前节点的 next 指向前一个节点，实现反转。将 prev 移动到当前节点 cur，为下一次迭代做准备。将 cur 移动到 temp，即当前节点的下一个节点，继续遍历链表。
返回新的头节点：循环结束后，cur 为 null，prev 指向反转后的链表的头节点。返回 prev 作为新的头节点。

代码

// 双指针
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        ListNode temp = null;
        while (cur != null) {
            temp = cur.next;// 保存下一个节点
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }
}

思路二：递归

主方法 reverseList：这个方法是对外的接口，接收链表的头节点 head。调用辅助方法 reverse，传入 null 作为前一个节点 pre 和 head 作为当前节点 cur。
辅助方法 reverse：这是一个递归方法，用于实际的链表反转操作。参数： pre：当前节点的前一个节点。cur：当前处理的节点。递归终止条件：当 cur 为 null 时，表示已经到达链表的末尾，此时 pre 就是反转后的链表的头节点，返回 pre。递归步骤：用 temp 保存 cur.next，即当前节点的下一个节点，防止在修改 cur.next 时丢失链表的后续部分。将 cur.next 指向 pre，即将当前节点的 next 指向前一个节点，实现反转。递归调用 reverse，传入 cur 作为新的 pre 和 temp 作为新的 cur，继续处理下一个节点。

代码：

class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null,head);        
    }
    private ListNode reverse(ListNode pre,ListNode cur){
        if(cur == null){
            return pre;
        }
        ListNode temp = null;
        temp = cur.next;
        cur.next = pre;
        //更新pre,cur位置
        // pre = cur
        // cur = temp
        return reverse(cur,temp);
    }
}