算法Day3|链表基础;203-移除链表元素;707-设计链表;206-反转链表前言 题目1: 203-移除链表元素 |

前言

• 题目1: 203-移除链表元素 | 2024-10-17(未通过) | 2024-10-18 (通过)
• 题目2：707-设计链表 | 2024-10-17(未通过) | 2024-10-18(通过)
• 题目3：206-反转链表 | 2024-10-18 (未通过)

1、链表理论基础

什么是链表？链表是一种通过指针串联在一起的线性结构，每个节点由一个数据域和一个指针域组成，最后一个节点的指针域指向 null（空指针）

链表的入口头节点就是 head。

当然，链表还有双链表和循环链表等类型，链表如何定义？

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

2、题目1：203-移除链表元素

题目：leetcode.cn/problems/re…

难度：简单

标签：链表

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

输入： head = [1,2,6,3,4,5,6], val = 6 输出： [1,2,3,4,5]

思路：使用虚拟头节点来完成元素的移除，这样就不需要考虑头节点的删除问题。

public ListNode removeElements(ListNode head,int val){
    ListNode dummy = new ListNode();
    dummy.next = head;
    ListNode pre = dummy;
    while (pre.next != null){
        if(pre.next.val == val){
            pre.next = pre.next.next;
        }else{
            pre = pre.next;
        }
    }
    return dummy.next;
}

3、题目2：707-设计链表

题目：leetcode.cn/problems/de…

难度：中等

实现 MyLinkedList 类：

• MyLinkedList() 初始化 MyLinkedList 对象。
• int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
• void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
• void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
• void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
• void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

自己来实现一个链表，并且实现这五个方法。

ok，那来设计链表。。

public class MyLinkedList {
    // 链表的长度
int size;
    ListNode head;

    public MyLinkedList(){
        this.size = 0;
        head = new ListNode();
    }

    // 获取链表中下标为 index 的节点的值，如果下标无效，则返回 -1
public int get(int index){
        if(index<0 || index>=size){
            return -1;
        }
        ListNode pre = head;
        // 包含一个虚拟头节点，所以查找index + 1
for (int i = 0; i <= index; i++) {
            pre = pre.next;
        }
        return pre.val;
    }

    // 将一个值为 val 的节点插入到链表的第一个元素之前
public void addAtHead(int val){
        ListNode node = new ListNode(val);
        node.next = head.next;
        head.next = node;
        size++;
    }

    // 将一个值为 val 的节点插入到最后一个元素
public void addAtTail(int val){
        ListNode node = new ListNode(val);
        ListNode pre = head;
        while (pre.next !=null){
            pre = pre.next;
        }
        pre.next = node;
        size++;
    }

    // 指定位置添加
public void addAtIndex(int index,int val){
        if(index<0){
            index =0;
        }
        if(index >size){
            return;
        }
        ListNode node = new ListNode(val);
        ListNode pre = head;
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }
        node.next = pre.next;
        pre.next = node;
        size++;
    }

    // 指定位置删除
public void deleteAtIndex(int index){
        if(index<0 || index>=size){
            return;
        }
        ListNode pre = head;
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }
        pre.next = pre.next.next;
        size--;
    }

}

4、题目3：206-反转链表

题目：leetcode.cn/problems/re…

难度：简单

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

首先定义一个 cur 指针，指向头结点，再定义一个 pre 指针，初始化为null ，利用temp 和双指针解决，流程图如下

public class Number206 {

    public ListNode reverseList(ListNode head) {
        // 首先给出两个指针
ListNode pre = null;
        ListNode curr = head;
        while (curr != null){
            ListNode temp = curr.next;
            curr.next = pre;
            pre = curr;
            curr = temp;
        }
        return pre;
    }
}

5、总结

• 1、虚拟头节点的目的是为了避免对头节点的特殊处理，涉及到对链表的修改就可以加个头节点。
• 2、双指针法在链表的反转中的应用，花流程图不会被绕