707.設(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
  

  提示：

• 0 <= index, val <= 1000
• 請(qǐng)不要使用內(nèi)置的 LinkedList 庫(kù)。
• 調(diào)用?get、addAtHead、addAtTail、addAtIndex?和?deleteAtIndex?的次數(shù)不超過(guò)?2000?。

單鏈表?

// 定義鏈表節(jié)點(diǎn)類
class ListNode {int val; // 節(jié)點(diǎn)存儲(chǔ)的值ListNode next; // 指向下一個(gè)節(jié)點(diǎn)的指針// 無(wú)參構(gòu)造方法ListNode() {}// 帶參數(shù)構(gòu)造方法ListNode(int val) {this.val = val;}
}// 實(shí)現(xiàn)單鏈表的類
class MyLinkedList {int size; // 鏈表的長(zhǎng)度（節(jié)點(diǎn)數(shù)）ListNode head; // 虛擬頭節(jié)點(diǎn)，方便統(tǒng)一操作// 初始化鏈表MyLinkedList() {head = new ListNode(0); // 初始化虛擬頭節(jié)點(diǎn)size = 0; // 初始化鏈表長(zhǎng)度為 0}// 獲取指定索引處的值public int get(int index) {// 如果索引非法，返回 -1if (index < 0 || index >= size) {return -1;}// 從虛擬頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)開(kāi)始遍歷ListNode cur = head.next;for (int i = 0; i < index; i++) {cur = cur.next; // 移動(dòng)到下一個(gè)節(jié)點(diǎn)}// 返回指定節(jié)點(diǎn)的值return cur.val;}// 在鏈表頭部插入值為 val 的節(jié)點(diǎn)public void addAtHead(int val) {// 創(chuàng)建新節(jié)點(diǎn)ListNode cur = new ListNode(val);// 新節(jié)點(diǎn)的 next 指向當(dāng)前鏈表的第一個(gè)節(jié)點(diǎn)cur.next = head.next;// 虛擬頭節(jié)點(diǎn)的 next 指向新節(jié)點(diǎn)head.next = cur;// 鏈表長(zhǎng)度加 1size++;}// 在鏈表尾部插入值為 val 的節(jié)點(diǎn)public void addAtTail(int val) {// 創(chuàng)建新節(jié)點(diǎn)ListNode cur = head; // 從虛擬頭節(jié)點(diǎn)開(kāi)始遍歷ListNode tail = new ListNode(val); // 新的尾部節(jié)點(diǎn)// 遍歷鏈表找到最后一個(gè)節(jié)點(diǎn)for (int i = 0; i < size; i++) {cur = cur.next;}// 將最后一個(gè)節(jié)點(diǎn)的 next 指向新節(jié)點(diǎn)cur.next = tail;// 鏈表長(zhǎng)度加 1size++;}// 在指定索引處插入值為 val 的節(jié)點(diǎn)public void addAtIndex(int index, int val) {// 如果索引超過(guò)當(dāng)前鏈表長(zhǎng)度，不進(jìn)行插入操作if (index > size) {return;}// 如果索引小于 0，將索引置為 0if (index < 0) {index = 0;}// 創(chuàng)建新節(jié)點(diǎn)ListNode cur = head; // 從虛擬頭節(jié)點(diǎn)開(kāi)始遍歷ListNode addNode = new ListNode(val); // 要插入的節(jié)點(diǎn)// 遍歷到指定索引位置的前一個(gè)節(jié)點(diǎn)for (int i = 0; i < index; i++) {cur = cur.next;}// 插入新節(jié)點(diǎn)addNode.next = cur.next; // 新節(jié)點(diǎn)的 next 指向當(dāng)前索引位置的節(jié)點(diǎn)cur.next = addNode; // 當(dāng)前節(jié)點(diǎn)的 next 指向新節(jié)點(diǎn)size++; // 鏈表長(zhǎng)度加 1}// 刪除指定索引處的節(jié)點(diǎn)public void deleteAtIndex(int index) {// 如果索引非法，不進(jìn)行刪除操作if (index < 0 || index >= size) {return;}// 從虛擬頭節(jié)點(diǎn)開(kāi)始遍歷ListNode cur = head;// 遍歷到指定索引位置的前一個(gè)節(jié)點(diǎn)for (int i = 0; i < index; i++) {cur = cur.next;}// 刪除節(jié)點(diǎn)：當(dāng)前節(jié)點(diǎn)的 next 指向被刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)cur.next = cur.next.next;size--; // 鏈表長(zhǎng)度減 1}
}

雙鏈表

class ListDoubleNode{int val;ListDoubleNode prev,next;ListDoubleNode(){};ListDoubleNode(int val){this.val=val;};
}
class MyLinkedListSolution1 {int size;ListDoubleNode head,tail;public MyLinkedListSolution1() {//初始化操作this.size = 0;this.head = new ListDoubleNode(0);this.tail = new ListDoubleNode(0);//這一步非常關(guān)鍵，否則在加入頭結(jié)點(diǎn)的操作中會(huì)出現(xiàn)null.next的錯(cuò)誤！！！head.next=tail;tail.prev=head;}public int get(int index) {//判斷index是否有效if(index>=size){return -1;}ListDoubleNode cur = this.head;//判斷是哪一邊遍歷時(shí)間更短if(index >= size / 2){//tail開(kāi)始cur = tail;for(int i=0; i< size-index; i++){cur = cur.prev;}}else{for(int i=0; i<= index; i++){cur = cur.next;}}return cur.val;}public void addAtHead(int val) {//等價(jià)于在第0個(gè)元素前添加addAtIndex(0,val);}public void addAtTail(int val) {//等價(jià)于在最后一個(gè)元素(null)前添加addAtIndex(size,val);}public void addAtIndex(int index, int val) {//index大于鏈表長(zhǎng)度if(index>size){return;}size++;//找到前驅(qū)ListDoubleNode pre = this.head;for(int i=0; i<index; i++){pre = pre.next;}//新建結(jié)點(diǎn)ListDoubleNode newNode = new ListDoubleNode(val);newNode.next = pre.next;pre.next.prev = newNode;newNode.prev = pre;pre.next = newNode;}public void deleteAtIndex(int index) {//判斷索引是否有效if(index>=size){return;}//刪除操作size--;ListDoubleNode pre = this.head;for(int i=0; i<index; i++){pre = pre.next;}pre.next.next.prev = pre;pre.next = pre.next.next;}
}