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

​

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

思路

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

思路一：双指针

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

思路二：递归

1. 主方法 reverseList：这个方法是对外的接口，接收链表的头节点 head。调用辅助方法 reverse，传入 null 作为前一个节点 pre 和 head 作为当前节点 cur。
2. 辅助方法 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);
    }
}

​