707. 设计链表
思路
使用带虚拟头结点的单链表，简化插入和删除操作。
// 单链表
class MyLinkedList {// 链表结点class ListNode {int val;ListNode next;ListNode(int val) {this.val = val;}}// 单链表结点数量（不包括虚拟头结点）private int size;// 单链表的虚拟头结点private ListNode head;// 初始化链表public MyLinkedList() {this.size = 0;this.head = new ListNode(0);}// 获取第 index 个结点的值，index从0开始public int get(int index) {if (index < 0 || index >= size) { // index 非法，返回 -1return -1;}ListNode cur = head.next;while (index != 0) {cur = cur.next;index--;}return cur.val;}// 头插法public void addAtHead(int val) {ListNode newNode = new ListNode(val);newNode.next = head.next;head.next = newNode;size++;}// 尾插法public void addAtTail(int val) {ListNode newNode = new ListNode(val);ListNode cur = head;while (cur.next != null) {cur = cur.next;}cur.next = newNode;size++;}// 在第 index 个结点前插入一个结点public void addAtIndex(int index, int val) {if (index < 0 || index > size) return;ListNode newNode = new ListNode(val);ListNode cur = head;while (index != 0) {cur = cur.next;index--;}newNode.next = cur.next;cur.next = newNode;size++;}public void deleteAtIndex(int index) {if (index < 0 || index >= size) {return;}ListNode cur = head;while (index != 0) {cur = cur.next;index--;}cur.next = cur.next.next;size--;}
}