1. 题目

2. 思路

(1) 伪头结点+尾指针+计数

• 设置一个伪头结点，便于向头结点之前插入结点。

• 维护一个尾指针，时刻指向尾结点，便于向尾结点之后插入结点，任何一种插入结点的方式都要注意更新尾指针。

• 统计链表的长度，用于快速判断能否获取、删除、插入结点。

3. 代码

public class Test {public static void main(String[] args) {MyLinkedList myLinkedList = new MyLinkedList();myLinkedList.addAtHead(1);myLinkedList.addAtTail(3);myLinkedList.addAtIndex(1, 2);System.out.println(myLinkedList.get(1));myLinkedList.deleteAtIndex(1);System.out.println(myLinkedList.get(1));}
}class MyLinkedList {private ListNode head;private ListNode tail;private int count;public MyLinkedList() {head = new ListNode(0);tail = head;}public int get(int index) {if (index < 0 || index >= count) {return -1;}ListNode cur = head.next;while (index > 0) {cur = cur.next;index--;}return cur.val;}public void addAtHead(int val) {ListNode node = new ListNode(val);node.next = head.next;head.next = node;if (tail.next != null) {tail = tail.next;}count++;}public void addAtTail(int val) {ListNode node = new ListNode(val);tail.next = node;tail = node;count++;}public void addAtIndex(int index, int val) {if (index <= 0) {addAtHead(val);return;}if (index == count) {addAtTail(val);return;}if (index > count) {return;}ListNode cur = head;while (index > 0) {cur = cur.next;index--;}ListNode node = new ListNode(val);node.next = cur.next;cur.next = node;if (tail.next != null) {tail = tail.next;}count++;}public void deleteAtIndex(int index) {if (index < 0 || index >= count) {return;}ListNode cur = head;while (index > 0) {cur = cur.next;index--;}if (cur.next.next == null) {tail = cur;}cur.next = cur.next.next;count--;}
}class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}
}