// 0707. Design Linked List
class MyLinkedList {
private Node head;
private Node tail;
private int size;
public MyLinkedList() {
this.head = null;
this.tail = null;
this.size = 0;
}
public int get(int index) {
if (index < 0 || index >= this.size) return -1;
Node curr = this.head;
while (index > 0) {
--index;
curr = curr.next;
}
return curr.val;
}
public Node getNodeAt(int index) {
Node curr = head;
while (index > 0) {
--index;
curr = curr.next;
}
return curr;
}
public void addAtHead(int val) {
Node node = new Node(val);
if (this.size == 0) {
this.head = node;
this.tail = node;
} else {
node.next = this.head;
this.head = node;
}
++this.size;
}
public void addAtTail(int val) {
Node node = new Node(val);
if (this.size == 0) {
this.head = node;
this.tail = node;
} else {
this.tail.next = node;
this.tail = node;
}
++this.size;
}
public void addAtIndex(int index, int val) {
if (index < 0 || index > this.size) return;
if (index == 0) {
addAtHead(val);
} else if (index == this.size) {
addAtTail(val);
} else {
Node previous = getNodeAt(index - 1);
Node next = previous.next;
Node curr = new Node(val);
previous.next = curr;
curr.next = next;
++this.size;
}
}
public void deleteFirst() {
if (this.size == 0) return;
else if (this.size == 1) {
this.head = null;
this.tail = null;
} else {
Node curr = this.head;
Node next = curr.next;
curr.next = null;
this.head = next;
}
--this.size;
}
public void deleteLast() {
if (this.size == 0) return;
else if (this.size == 1) {
this.head = null;
this.tail = null;
} else {
Node secondLast = getNodeAt(this.size - 2);
secondLast.next = null;
this.tail = secondLast;
}
this.size--;
}
public void deleteAtIndex(int index) {
if (index < 0 || index >= this.size) return;
if (index == 0) {
deleteFirst();
} else if (index == this.size - 1) {
deleteLast();
} else {
Node previous = getNodeAt(index - 1);
Node curr = previous.next;
previous.next = previous.next.next;
--this.size;
}
}
}
class Node {
Node next = null;
int val = 0;
public Node(int val) {
this.val = val;
}
}
学习笔记： 今天这是一道设计题。 设计链表，链表是个比较有逻辑的数据结构。 先看了老外的代码，借鉴了不少，还进行了优化改良。 这里其实一共8个函数： 根据下标得到值， 根据下标得到结点，（题目没要求） 在头上加结点， 在尾上加结点， 根据下标加结点， 在头上删结点，（题目没要求） 在尾上删结点，（题目没要求） 根据下标删结点。 没要求的都会在其他函数中用得上，所以也就有了。 暂时没有去考虑双向链表的话怎么写，以后有空了得写写看。