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

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

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

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

實現(xiàn) MyLinkedList 類：

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

示例：

輸入
[“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é)點之后的長度ListNode head;//虛擬頭結(jié)點public MyLinkedList() {size=0; //初始化鏈表長度，但是設(shè)置虛擬頭結(jié)點的時候size不會加一head=new ListNode(-1,null); //設(shè)置的虛擬頭節(jié)點}public int get(int index) {//index從0開始，下面的情況非法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，說明是插在頭結(jié)點之前，令index=0//如果inde=size，說明要插在末尾//如果index>size,非法返回空if(index>size)return;if(index<0)index=0;//找到要插入的地方的前驅(qū)，方便操作(因為是虛擬指針，如果要找到index位置的元素，則使用i<index-1，// 現(xiàn)在是找到這個元素的前驅(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--;}
}