一纹蝴、題目
設計鏈表的實現(xiàn)。您可以選擇使用單鏈表或雙鏈表踪少。單鏈表中的節(jié)點應該具有兩個屬性：val 和 next塘安。val 是當前節(jié)點的值，next 是指向下一個節(jié)點的指針/引用援奢。如果要使用雙向鏈表兼犯，則還需要一個屬性 prev 以指示鏈表中的上一個節(jié)點。假設鏈表中的所有節(jié)點都是 0-index 的集漾。
在鏈表類中實現(xiàn)這些功能：
get(index) ：獲取鏈表中第
index個節(jié)點的值切黔。如果索引無效，則返回-1帆竹。
addAtHead(val) ：在鏈表的第一個元素之前添加一個值為val的節(jié)點绕娘。插入后脓规，新節(jié)點將成為鏈表的第一個節(jié)點栽连。
addAtTail(val) ：將值為val的節(jié)點追加到鏈表的最后一個元素。
addAtIndex(index,val) ：在鏈表中的第index個節(jié)點之前添加值為val的節(jié)點。如果index等于鏈表的長度秒紧，則該節(jié)點將附加到鏈表的末尾绢陌。如果index大于鏈表長度，則不會插入節(jié)點熔恢。如果index小于0脐湾，則在頭部插入節(jié)點。
deleteAtIndex(index) ：如果索引index有效叙淌，則刪除鏈表中的第index個節(jié)點秤掌。
二、示例
2.1> 示例：
MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //鏈表變?yōu)?-> 2-> 3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //現(xiàn)在鏈表是1-> 3
linkedList.get(1); //返回3
提示：
- 所有
val值都在[1, 1000]之內鹰霍。 - 操作次數(shù)將在
[1, 1000]之內闻鉴。 - 請不要使用內置的 LinkedList 庫。
三茂洒、解題思路
其實這類題就是讓我們自己去實現(xiàn)容器孟岛，跟設計HashSet、設計HashMap督勺、設計Deque等等是一類題渠羞。對于Java實現(xiàn)來說，我們只需要參照LinkedList即可智哀。
當然次询，在JDK中LinkedList是采用雙向鏈表實現(xiàn)的底層邏輯。此處與單向鏈表實現(xiàn)區(qū)別不大瓷叫。
這道題就不畫圖了渗蟹，具體代碼請參照——代碼實現(xiàn)。
四赞辩、代碼實現(xiàn)
class MyLinkedList {
private Node first = null;
private Node last = null;
private int size = 0;
public MyLinkedList() {
}
public int get(int index) {
if (!isElementIndex(index)) return -1;
return getNode(index).val;
}
public void addAtHead(int val) {
Node newNode = new Node(null, val, first);
if (first != null) first.prev = newNode;
first = newNode;
if (last == null) last = first;
size++;
}
public void addAtTail(int val) {
Node newNode = new Node(last, val, null);
if (last != null) last.next = newNode;
last = newNode;
if (first == null) first = last;
size++;
}
public void addAtIndex(int index, int val) {
if (index > size) return;
if (index == size) {
addAtTail(val);
} else if (index <= 0) {
addAtHead(val);
} else {
Node node = getNode(index);
Node newNode = new Node(node.prev, val, node);
if (node.prev != null) node.prev.next = newNode;
node.prev = newNode;
size++;
}
}
public void deleteAtIndex(int index) {
if (!isElementIndex(index)) return;
Node node = getNode(index);
if (index == 0) {
first = node.next;
if (size > 1) node.next.prev = null;
node.next = null;
} else if (index == size - 1) {
last = node.prev;
if (size > 1) node.prev.next = null;
node.prev = null;
} else {
node.prev.next = node.next;
node.next.prev = node.prev;
}
size--;
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
public Node getNode(int index) {
if (!isElementIndex(index)) return null;
if (index < (size >> 1)) {
Node x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
private static class Node {
int val;
Node next, prev;
Node(Node prev, int val, Node next) {
this.val = val;
this.next = next;
this.prev = prev;
}
}
}
今天的文章內容就這些了：
寫作不易雌芽，筆者幾個小時甚至數(shù)天完成的一篇文章，只愿換來您幾秒鐘的 點贊 & 分享 辨嗽。
更多技術干貨世落，歡迎大家關注公眾號“爪哇繆斯” ~ \(o)/ ~ 「干貨分享，每天更新」
