本文主要是介绍力扣刷题--设计链表707,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
这个题目的难点:
- 确定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;}
}
再设计一个自己的链表
对于一个链表,有两个成员成员变量:、
- size(记录链表长度)
- 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-1if (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需要遍历几次,找到什么位置。
插入的时候的步骤顺序不能反了,否则会出现找不到下一个结点的状况。
这篇关于力扣刷题--设计链表707的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!