本题需要在链表类中实现这些功能：
-
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
-
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
-
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
-
addAtIndex(index,val)：在链表中的第index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index
大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点 -
deleteAtIndex(index)：如果索引 index有效，则删除链表中的第 index 个节点。
分析：addAtHead(val)，addAtTail(val)均可以通过addAtIndex(index,val)函数来实现，即：addAtIndex(0,val); addAtIndex(size,val); 其中链表长度为size，index的取值范围为[0,size-1]；
java单链表数据结构：
class ListNode{
int val;
ListNode next;
ListNode(){}
ListNode(int val){
this.val = val;
}
}
完整代码：
class MyLinkedList {
int size;
ListNode head;
public MyLinkedList() {
size = 0;
//虚拟头结点
head = new ListNode(0);
}
public int get(int index) {
if(index < 0 || index >= size) return -1; //链表索引index的取值范围[0,size-1]
ListNode cur = head;
//本链表已包含虚拟头结点，因而需要寻找索引为index+1的节点
for(int i=0; i<=index; i++) {
cur = cur.next;
}
return cur.val;
}
public void addAtHead(int val) {
addAtIndex(0, val);
}
public void addAtTail(int val) {
addAtIndex(size, val);
}
public void addAtIndex(int index, int val) {
//在链表中的第index 个节点之前添加值为val的节点
//index <= 0 插入在头部，虚拟结点后面
//index == size 插入到结尾
//index > size 不插入结点。
if(index > size) return ;
if(index <= 0){
index = 0;
}
size++;
//本要插入到索引为index-1的结点之后，现在要插入到索引为index的节点之后，
ListNode addNode = new ListNode(val);
ListNode cur = head;
for(int i=0; i<index; i++) {
cur = cur.next;
}
addNode.next = cur.next;
cur.next = addNode;
}
public void deleteAtIndex(int index) {
if(index < 0 || index >= size) return ;
ListNode cur = head;
size-- ;
for(int i=0; i<index; i++) {
cur = cur.next;
}
cur.next = cur.next.next;
}
}
java双链表数据结构：
class ListNode{
int val;
ListNode prev,next;
ListNode(){}
ListNode(int x){ val = x; }
}
完整代码：
class MyLinkedList {
class ListNode{
int val;
ListNode next,prev;
ListNode(int x){ val = x; }
}
int size;
ListNode head, tail;
public MyLinkedList() {
size = 0;
//虚拟头结点
head = new ListNode(0);
tail = new ListNode(0);
head.next = tail;
tail.prev = head; //为什么是这样的？？？
}
public ListNode get_(int index){
ListNode cur;
if(index < (size-1)/2){
cur = head;
for(int i=0; i<=index ;i++){
cur = cur.next;
}
}
else{
cur = tail;
for(int i=0;i<=size-1-index;i++){
cur = cur.prev;
}
}
return cur;
}
public int get(int index) {
if(index >= size || index < 0) return -1;
ListNode cur = get_(index);
return cur.val;
}
public void addAtHead(int val) {
ListNode addhead = new ListNode(val);
addhead.next = head.next;
head.next.prev = addhead;
head.next = addhead;
addhead.prev = head;
size++;
}
public void addAtTail(int val) {
ListNode addtail = new ListNode(val);
tail.prev.next = addtail;
addtail.prev = tail.prev;
addtail.next = tail;
tail.prev = addtail;
size++;
}
public void addAtIndex(int index, int val) {
if(index>size) return;
if (index<0) index = 0;
size++;
ListNode cur = head;
for(int i=0; i<index; i++){
cur = cur.next;
}
ListNode addnode = new ListNode(val);
addnode.next = cur.next;
addnode.next.prev = addnode;
cur.next = addnode;
addnode.prev = cur;
}
public void deleteAtIndex(int index) {
if(index<0 || index>=size) return;
ListNode cur = head;
for(int i=0; i<index; i++){
cur = cur.next;
}
cur.next.next.prev = cur;
cur.next = cur.next.next;
size--;
return ;
}
}
