力扣刷题--设计链表707

发布时间:2024年01月11日

这个题目的难点:

  • 确定index是什么,index的范围
  • 向后遍历的次数,也就是循环的次数
  • 在某处添加或者删除一个结点,需要找到它的前一个结点

在这里插入图片描述

单链表

首先对于创建一个链表,需要单链表结构

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

再设计一个自己的链表
对于一个链表,有两个成员成员变量:、

  1. size(记录链表长度)
  2. head(一个虚拟头结点)

初始化一个链表:

//    初始化这个链表
    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);  //创建一个虚拟头节点
    }

获取索引处的数值

在这里插入图片描述
比如上图,要找index=2时候的数值:
首先确定index的范围是否有效:if (index < 0 || index >= size)
找到index这个节点 for(int i = 0; i <= index; i++)

    //获取索引处的数值
    //获取索引处的数值
    public int get(int index) {
        //index范围: 0,size-1
        if (index >= size || index <0){
            return -1;
        }
        ListNode cur = head;
        //因为包含一个虚拟头节点 所以要多移动一位
        for (int i = 0; i <= index; i++) {
            cur= cur.next;
        }
        return cur.val;
    }

在头处加入数值

在这里插入图片描述

不需要进行任何判断,因为虚拟头节点一直都在。
需要注意的是插入步骤不能反了,否则会出现指针丢失,找不到下一个节点的状况。

  //也就是在head节点和第一个节点直接加入一个节点
    public void addAtHead(int val) {
        ListNode temp = new ListNode(val);
        temp.next =head.next;
        head.next = temp;
        size++;
    }

在最后加入一个数值

在这里插入图片描述
先找到最后一个节点:也就是cur的遍历次数:for(int i = 0; i < size ; i++)
再进行插入。

 
    public void addAtTail(int val) {
        ListNode cur = head;
        for (int i = 0; i < size; i++) {
            cur = cur.next;
        }
        ListNode temp = new ListNode(val);
        cur.next = temp;
        temp.next = null;
        size++;
    }

在索引处加入一个数值

首先需要明确的是插入的index的范围:
值得注意的是index=size这个地方可能会被遗漏,index的范围是[0,size-1],但是插入的时候,index=size是可以的,这相当于在当前列表的最后插入了一个节点。
在这里插入图片描述
然后是插入步骤
比如要在index=3这个地方插入一个结点,需要先找到index=2这个地方,用i进行循环遍历,i的范围为for(int i = 0 ; i < index ; i++)
需要注意的是,在index处插入一个结点,需要找到它的前一个结点,而不是找到它这个结点。
比如下图的temp插入后就成了链表中 index = 3 的结点。
插入的顺序也需要注意一下。
在这里插入图片描述

	public void addAtIndex(int index, int val) {
        if (index > size){
            return;
        }
        if (index < 0){
            index = 0;
        }
        ListNode cur = head;
        //找到要插入处的前一个节点
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        ListNode temp = new ListNode(val);
        temp.next = cur.next;
        cur.next = temp;
        size++;
    }

删除索引处的元素

首先需要确定的是可以删除的index的范围:[0,size-1] (如图所示红色的index部分)
然后需要注意的是,删除一个结点,需要找到它的前一个结点,比如图中,需要删除index=2处的结点,需要找到index=1处的结点,也就是i的循环范围是for(int i = 0 ; i < index ; i ++) ,再执行删除操作,此处的删除操作很简单,就是是得cur.next = cur.next.next.

在这里插入图片描述


    public void deleteAtIndex(int index) {
        if (index < 0){
            return;
        }
        if (index >= size){
            return;
        }
        ListNode cur = head;
        //找到这个索引的前一个节点
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        size--;
    }

总结:
链表中需要注意的就是index的范围,每次cur遍历,cur需要遍历几次,找到什么位置。
插入的时候的步骤顺序不能反了,否则会出现找不到下一个结点的状况。

文章来源:https://blog.csdn.net/weixin_45332508/article/details/135518266
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。