文章目录
前言
哈喽，我是长路，目前刚刚大三，方向是后端也偶尔捣鼓下前端，现在的主语言是Java。之前一大段时间都是在学习web开发的一些技术，就很久没有进行类似于数据结构、算法之类的学习与刷题，打算这段时间拾起来好好学一学、搞一搞。
这段时间也是机缘巧合看到草帽路飞的博客，加了自学群，正巧看到博主组织在群里组织了leetcode刷题打卡活动，我也就参与进来，为期一个月，打算坚持每天都花一些时间做一些题目，并通过博客的方式来进行记录。
目前跟着一个Github仓库刷题(leetcode)：代码随想录leetcode刷题，当前为链表专题。
题目
题目来源leetcode
leetcode地址：707. 设计链表，难度：中等。
题目描述(摘自leetcode)：
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
示例：
MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //现在链表是1-> 3
linkedList.get(1); //返回3
提示：
所有val值都在 [1, 1000] 之内。
操作次数将在 [1, 1000] 之内。
请不要使用内置的 LinkedList 库。
本地调试代码：
class MyLinkedList {
public MyLinkedList() {
}
public int get(int index) {
}
public void addAtHead(int val) {
}
public void addAtTail(int val) {
}
public void addAtIndex(int index, int val) {
}
public void deleteAtIndex(int index) {
}
public static void main(String[] args) {
MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1); printLinked(linkedList);
linkedList.addAtTail(3); printLinked(linkedList);
linkedList.addAtIndex(1,2); printLinked(linkedList); //链表变为1-> 2-> 3
System.out.println(linkedList.get(1)); //返回2
linkedList.deleteAtIndex(1); printLinked(linkedList); //现在链表是1-> 3
System.out.println(linkedList.get(1)); //返回3
}
public static void printLinked(MyLinkedList linkedList){
ListNode node = linkedList.head;
if(node == null){
return;
}
System.out.print("[");
while(node!=null){
System.out.print(node.val);
node = node.next;
}
System.out.print("]");
System.out.println();
}
}
题解
写前注意点(2点)
①注意下面这句话，第 index 个节点之前添加值为 val 的节点实际上与后面等于链表的长度不冲突，只需要把等于条件放在前面即可。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
②注意点(坑点)：红框勾选的一个是获取，一个是删除，注意题目写的是获取或删除第index个节点，从字面上来看传入1，就是删除掉链表中的第一个元素，而实际上则是需要你删除或获取到索引为index的元素，传入1实际上是删除或获取索引为1的元素。
NO1：单向链表实现
思路：这里的话是单向链表实现，每个节点只有一个后置节点，特别的注意点就是我上面提到的两点，其他的我觉得没什么需要提的，主要看下面代码实现。
代码：
class MyLinkedList {
private ListNode head;//头节点
private ListNode tail;//尾结点
private int size;//节点数量
class ListNode{
private int val;
private ListNode next;
public ListNode(int val,ListNode next) {
this.val = val;
this.next = next;
}
}
public MyLinkedList() {
this.head = null;
this.tail = null;
this.size = 0;
}
public int get(int index) {
if(!checkExists(index)){
return -1;
}
ListNode cur = this.head;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur.val;
}
public void addAtHead(int val) {
ListNode newHead = new ListNode(val, this.head);
//更新尾结点
if(this.tail == null){
this.tail = newHead;
}
//更新头节点
this.head = newHead;
this.size++;
}
public void addAtTail(int val) {
ListNode newTail = new ListNode(val, null);
//更新尾结点
this.tail = newTail;
//处理无头节点情况
if(this.head == null){
this.head = newTail;
}else{
//遍历到尾节点插入
ListNode cur = this.head;
for (int i = 0; i < this.size-1; i++) {
cur = cur.next;
}
cur.next = newTail;
}
this.size++;
}
public void addAtIndex(int index, int val) {
//情况1：index>size，不插入节点
if(index > this.size){
return;
}
//情况2：index<0，在头部插入节点（包含index=0情况）
if(index <= 0){
this.addAtHead(val);
return;
}
//情况3：index=size，添加到链表末尾
if(index == this.size){
this.addAtTail(val);
return;
}
//最终情况：在指定index位置前插入
ListNode newNode = new ListNode(val, null);
ListNode pre = this.head;
//当前数量>1，index>1情况，找到前置节点
for (int i = 1; i < index; i++) {
pre = pre.next;
}
//插入节点操作
newNode.next = pre.next;
pre.next = newNode;
this.size++;
}
public void deleteAtIndex(int index) {
if(!checkExists(index)){
return;
}
//情况1：index=0情况
if(index == 0){
this.head = this.head.next;
if(size == 1){
this.tail = null; //若是当前数量也为1，尾节点也要删除
}
this.size--;
return;
}
//定位到要删除的指定节点前一个
ListNode cur = head;
for (int i = 1; i < index; i++) {
cur = cur.next;
}
//判断是否是尾节点，是的话更新尾节点
if(cur.next == this.tail){
this.tail = cur;
}else{
//删除指定节点
cur.next = cur.next.next;
}
this.size--;
}
//检查当前链表索引是否存在
public boolean checkExists(int index){
if(index < 0 || index >= size){
return false;
}
return true;
}
}
NO2：双向链表实现
案例参考leetcode题解的某个评论：我是理解了jdk-8 LinkedList源码写出来的 有不对的地方，希望指正
使用双向链表的话其实就更加轻松一点，并且在本案例中对于方法重用的设计也更加巧妙！
思路：主要每个节点就是设置了一个前置节点和一个后置节点，相对于前面的单向链表多了一个前置节点。
代码：
class MyLinkedList {
private class Node{
public int val;
public Node next;
public Node prev;
Node(int val){
this.val = val;
}
Node(Node prev,int val,Node next){
this.prev = prev;
this.val = val;
this.next = next;
}
}
//头节点
private Node first;
//尾结点
private Node last;
//链表长度
private int size;
public MyLinkedList() {
this.first = null;
this.last = null;
this.size = 0;
}
public boolean checkIndex(int index){
if(index<0 || index>=size){
return false;
}
return true;
}
public int get(int index) {
if(!checkIndex(index)){
return -1;
}
if(index == 0){
return this.first.val;
}else if(index == this.size-1){
return this.last.val;
}else{
return indexOf(index).val;
}
}
private Node indexOf(int index) {
//判断当前索引在链表中的大致位置，若是在左边优先从头节点遍历
if(index < size>>1 ){
Node cur = this.first;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur;
}else{//从后向前遍历
Node cur = this.last;
for (int i = 1 ;i< this.size-index; i++) {
cur = cur.prev;
}
return cur;
}
}
public void addAtHead(int val) {
//记录保存一下当前的第一个节点
Node f = this.first;
Node newNode = new Node(null, val, f);
this.first = newNode;//更新一下头节点
//如果原本第一个节点为null，说明原本链表为空，此时尾结点也肯定为空
if(f == null){
this.last = newNode;
}else{
f.prev = newNode;//原本的前置节点进行更新
}
this.size++;
}
public void addAtTail(int val) {
//记录保存一下当前的尾节点
Node l = this.last;
Node newNode = new Node(l, val, null);
this.last = newNode;//更新一下尾节点
if(l == null){
this.first = newNode;
}else{
l.next = newNode;//更新一下当前头节点
}
this.size++;
}
public void addAtIndex(int index, int val) {
if(index == 0){
this.addAtHead(val);
}else if(index == this.size){
this.addAtTail(val);
}else if(index>this.size){
return;
}else{
//此时index是在当前链表必存在的情况
add(index,val);
}
}
public void add(int index, int val) {
Node cur = indexOf(index);
Node preNode = cur.prev;
Node newNode = new Node(preNode, val, cur);
//更新索引为index节点的后置节点为新节点
preNode.next = newNode;
cur.prev = newNode;
this.size++;
}
public void deleteAtIndex(int index) {
if(!checkIndex(index)){
return;
}
//当前节点数量=1情况
if(this.size == 1){
this.size--;
this.first = null;
this.last = null;
return;
}
//当前节点数量>1情况：找到指定要删除的节点
Node delNode = indexOf(index);
//删除节点为头节点情况
if(index == 0){
this.first = delNode.next;
this.first.prev = null;
}else if(index == this.size-1){//为尾结点情况
this.last = this.last.prev;
this.last.next = null;
}else{
//中间情况，前后节点都要进行更新
delNode.prev.next = delNode.next;
delNode.next.prev = delNode.prev;
}
this.size--;
}
}
参考资料
[1]. leetcode评论
[2]. 代码随想录—707.设计链表
我是长路，感谢你的耐心阅读。如有问题请指出，我会积极采纳！ 欢迎关注我的公众号【长路Java】，分享Java学习文章及相关资料 Q群：851968786 我们可以一起探讨学习 注明：转载可，需要附带上文章链接
整理者：长路 时间：2021.10.15
评论区请在客户端页面查看