題目：leetcode707. 設(shè)計(jì)鏈表

描述：
你可以選擇使用單鏈表或者雙鏈表，設(shè)計(jì)并實(shí)現(xiàn)自己的鏈表。

單鏈表中的節(jié)點(diǎn)應(yīng)該具備兩個(gè)屬性：val 和 next 。val 是當(dāng)前節(jié)點(diǎn)的值，next 是指向下一個(gè)節(jié)點(diǎn)的指針/引用。

如果是雙向鏈表，則還需要屬性 prev 以指示鏈表中的上一個(gè)節(jié)點(diǎn)。假設(shè)鏈表中的所有節(jié)點(diǎn)下標(biāo)從 0 開(kāi)始。

實(shí)現(xiàn) MyLinkedList 類：

MyLinkedList() 初始化 MyLinkedList 對(duì)象。
int get(int index) 獲取鏈表中下標(biāo)為 index 的節(jié)點(diǎn)的值。如果下標(biāo)無(wú)效，則返回 -1 。
void addAtHead(int val) 將一個(gè)值為 val 的節(jié)點(diǎn)插入到鏈表中第一個(gè)元素之前。在插入完成后，新節(jié)點(diǎn)會(huì)成為鏈表的第一個(gè)節(jié)點(diǎn)。
void addAtTail(int val) 將一個(gè)值為 val 的節(jié)點(diǎn)追加到鏈表中作為鏈表的最后一個(gè)元素。
void addAtIndex(int index, int val) 將一個(gè)值為 val 的節(jié)點(diǎn)插入到鏈表中下標(biāo)為 index 的節(jié)點(diǎn)之前。如果 index 等于鏈表的長(zhǎng)度，那么該節(jié)點(diǎn)會(huì)被追加到鏈表的末尾。如果 index 比長(zhǎng)度更大，該節(jié)點(diǎn)將 不會(huì)插入 到鏈表中。
void deleteAtIndex(int index) 如果下標(biāo)有效，則刪除鏈表中下標(biāo)為 index 的節(jié)點(diǎn)。

示例：

輸入
[“MyLinkedList”, “addAtHead”, “addAtTail”, “addAtIndex”, “get”, “deleteAtIndex”, “get”]
[[], [1], [3], [1, 2], [1], [1], [1]]
輸出
[null, null, null, null, 2, null, 3]

解釋
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2); // 鏈表變?yōu)?1->2->3
myLinkedList.get(1); // 返回 2
myLinkedList.deleteAtIndex(1); // 現(xiàn)在，鏈表變?yōu)?1->3
myLinkedList.get(1); // 返回 3

思路：使用單鏈表+虛擬指針完成

public class ListNode {public int val;public ListNode next;public ListNode(){};public ListNode(int val){ this.val=val;}public ListNode(int val, ListNode next) {this.val = val;this.next = next;}
}public class MyLinkedList {int size; //除去虛擬頭結(jié)點(diǎn)之后的長(zhǎng)度ListNode head;//虛擬頭結(jié)點(diǎn)public MyLinkedList() {size=0; //初始化鏈表長(zhǎng)度，但是設(shè)置虛擬頭結(jié)點(diǎn)的時(shí)候size不會(huì)加一head=new ListNode(-1,null); //設(shè)置的虛擬頭節(jié)點(diǎn)}public int get(int index) {//index從0開(kāi)始，下面的情況非法if(index<0||index>=size)return -1;ListNode cur=head.next;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<0，說(shuō)明是插在頭結(jié)點(diǎn)之前，令index=0//如果inde=size，說(shuō)明要插在末尾//如果index>size,非法返回空if(index>size)return;if(index<0)index=0;//找到要插入的地方的前驅(qū)，方便操作(因?yàn)槭翘摂M指針，如果要找到index位置的元素，則使用i<index-1，// 現(xiàn)在是找到這個(gè)元素的前驅(qū)，則i<index)ListNode pre=head;for (int i = 0; i < index; i++) {pre=pre.next;}ListNode newNode=new ListNode(val);newNode.next=pre.next;pre.next=newNode;size++;}public void deleteAtIndex(int index) {if(index<0||index>size-1)return;//使用雙指針進(jìn)行刪除操作ListNode pre=head;ListNode cur=head.next;for(int i=0;i<index;i++){cur=cur.next;pre=pre.next;}pre.next=cur.next;size--;}
}