LeetCode鏈接：https://leetcode.cn/problems/design-linked-list/

題目：設計鏈表的實作，您可以選擇使用單鏈表或雙鏈表，單鏈表中的節點應該具有兩個屬性：val 和 next，val 是當前節點的值，next 是指向下一個節點的指標/參考，如果要使用雙向鏈表，則還需要一個屬性 prev 以指示鏈表中的上一個節點，假設鏈表中的所有節點都是 0-index 的，

在鏈表類中實作這些功能：

get(index)：獲取鏈表中第 index 個節點的值，如果索引無效，則回傳-1，
addAtHead(val)：在鏈表的第一個元素之前添加一個值為 val 的節點，插入后，新節點將成為鏈表的第一個節點，
addAtTail(val)：將值為 val 的節點追加到鏈表的最后一個元素，
addAtIndex(index,val)：在鏈表中的第 index 個節點之前添加值為 val 的節點，如果 index 等于鏈表的長度，則該節點將附加到鏈表的末尾，如果 index 大于鏈表長度，則不會插入節點，如果index小于0，則在頭部插入節點，
deleteAtIndex(index)：如果索引 index 有效，則洗掉鏈表中的第 index 個節點，

示例1：

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //鏈表變為1-> 2-> 3
linkedList.get(1); //回傳2
linkedList.deleteAtIndex(1); //現在鏈表是1-> 3
linkedList.get(1); //回傳3

思路

洗掉鏈表節點：

添加鏈表節點：

這道題目設計鏈表的五個介面：

獲取鏈表第index個節點的數值
在鏈表的最前面插入一個節點
在鏈表的最后面插入一個節點
在鏈表第index個節點前面插入一個節點
洗掉鏈表的第index個節點

可以說這五個介面，已經覆寫了鏈表的常見操作，是練習鏈表操作非常好的一道題目

鏈表操作的兩種方式：

直接使用原來的鏈表來進行操作，
設定一個虛擬頭結點在進行操作，

下面采用的設定一個虛擬頭結點（這樣更方便一些，大家看代碼就會感受出來）

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;         }         ListNode curr=head;         for(int i=0; i<=index; i++){             curr=curr.next;         }         return curr.val;     }          public void addAtHead(int val) {         addAtIndex(0,val);     }          public void addAtTail(int val) {         addAtIndex(size,val);     }          public void addAtIndex(int index, int val) {         if(index>size){             return;         }         if(index<0){             index=0;         }         size++;         ListNode curr=head;         ListNode ne=new ListNode(val);         for(int i=0; i<index; i++){             curr=curr.next;         }         ne.next=curr.next;         curr.next=ne;     }          public void deleteAtIndex(int index) {         if(index<0 || index>=size){             return;         }         size--;         ListNode curr=head;         for(int i=0; i<index; i++){             curr=curr.next;         }         curr.next=curr.next.next;     } }

首先我們自己定義一個ListNode節點，設計一個鏈表里面有兩個屬性，一個大小，一個節點，首先先初始化一個鏈表，并且有一個虛擬頭結點，然后開始第一個獲取功能，主要是要回圈index+1次，因為包括了頭結點，對于增加節點功能，得判斷輸入的情況，再回圈index次，使用上面提到的增加節點方法即可（size要+1），對于洗掉節點，同樣也要回圈index次，使用上面提到的方法洗掉即可（size要-1），最后在頭尾插入元素，呼叫實作的插入函式即可，

這是一道基礎題，不難，但是一定要掌握，否則基礎沒過關，后面題沒法弄！！！

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/538952.html

標籤：其他

上一篇：力扣02 兩數相加

下一篇：劍指offer題解C++版

設計鏈表-LeetCode707 基礎題

思路