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)的指針/引用鄙煤。如果要使用雙向鏈表晾匠，則還需要一個(gè)屬性 prev 以指示鏈表中的上一個(gè)節(jié)點(diǎn)。假設(shè)鏈表中的所有節(jié)點(diǎn)都是 0-index 的梯刚。
在鏈表類中實(shí)現(xiàn)這些功能：
get(index)：獲取鏈表中第 index 個(gè)節(jié)點(diǎn)的值凉馆。如果索引無效，則返回-1亡资。
addAtHead(val)：在鏈表的第一個(gè)元素之前添加一個(gè)值為 val 的節(jié)點(diǎn)澜共。插入后，新節(jié)點(diǎn)將成為鏈表的第一個(gè)節(jié)點(diǎn)锥腻。
addAtTail(val)：將值為 val 的節(jié)點(diǎn)追加到鏈表的最后一個(gè)元素嗦董。
addAtIndex(index,val)：在鏈表中的第 index 個(gè)節(jié)點(diǎn)之前添加值為 val 的節(jié)點(diǎn)。如果 index 等于鏈表的長度瘦黑，則該節(jié)點(diǎn)將附加到鏈表的末尾京革。如果 index 大于鏈表長度，則不會(huì)插入節(jié)點(diǎn)幸斥。
deleteAtIndex(index)：如果索引 index 有效匹摇，則刪除鏈表中的第 index 個(gè)節(jié)點(diǎn)。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/design-linked-list
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有甲葬。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)廊勃，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
-
1.虛擬頭節(jié)點(diǎn)
思路：
1.通過維護(hù)一個(gè)虛擬的頭節(jié)點(diǎn)dummyHead來操作鏈表经窖，從而實(shí)現(xiàn)添加和刪除操作坡垫。
public class MyLinkedList {
private class Node {
public int val;
public Node next;
public Node(int val, Node next) {
this.val = val;
this.next = next;
}
public Node(int val) {
this(val, null);
}
public Node() {
this(0, null);
}
}
//使用虛擬頭節(jié)點(diǎn)
private Node dummyHead;
private int size;
/**
* Initialize your data structure here.
*/
public MyLinkedList() {
dummyHead = new Node();
size = 0;
}
/**
* Get the value of the index-th node in the linked list. If the index is invalid, return -1.
*/
public int get(int index) {
if (index < 0 || index >= size) return -1;
Node cur = dummyHead.next; //頭節(jié)點(diǎn)
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur.val;
}
/**
* judge linked list is empty?
*/
public boolean isEmpty() {
return size == 0;
}
/**
* Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
*/
public void addAtHead(int val) {
addAtIndex(0, val);
}
/**
* Append a node of value val to the last element of the linked list.
*/
public void addAtTail(int val) {
addAtIndex(size, val);
}
/**
* Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
*/
public void addAtIndex(int index, int val) {
if (index < 0 || index > size) {
return;
}
Node prev = dummyHead;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
prev.next = new Node(val, prev.next);
size++;
}
/**
* Delete the index-th node in the linked list, if the index is valid.
*/
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) throw new IllegalArgumentException("Add filed, index is illegal");
Node prev = dummyHead;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
Node retNode = prev.next;
prev.next = retNode.next;
retNode.next = null; //loitering object != memory leak
size--;
}
}
-
2.常規(guī)解法
思路：
通過維護(hù)當(dāng)前節(jié)點(diǎn)cur完成相關(guān)操作
public class MyLinkedList2 {
private class Node {
private int val;
private Node next;
public Node(int val, Node next) {
this.val = val;
this.next = next;
}
public Node(int val) {
this(val, null);
}
public Node() {
this(0, null);
}
}
private Node head;
private int size;
public MyLinkedList2() {
head = null;
size = 0;
}
public void addAtHead(int val) {
// Node node = new Node(val);
// node.next = head;
// head = node;
head = new Node(val, head);
size ++;
}
public void addAtIndex(int index, int val) {
if (index < 0 || index > size) {
return;
}
if (index == 0) {
addAtHead(val);
} else {
Node prev = head;
for (int i = 0; i < index - 1; i++) {
prev = prev.next;
}
prev.next = new Node(val, prev.next);
size ++;
}
}
public void deleteAtHead() {
head = head.next;
size--;
}
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) {
return;
}
if (index == 0) {
deleteAtHead();
} else {
Node prev = head;
for (int i = 0; i < index - 1; i++) {
prev = prev.next;
}
Node cur = prev.next;
prev.next = cur.next;
cur.next = null;
size--;
}
}
public void addAtTail(int val) {
addAtIndex(size, val);
}
public int get(int index) {
if (index < 0 || index >= size) {
return -1;
}
if (index == 0) {
return head.val;
} else {
Node cur = head.next;
for (int i = 0; i < index - 1; i++) {
cur = cur.next;
}
return cur.val;
}
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
Node cur = head;
while (cur != null) {
res.append(cur.val + "->");
cur = cur.next;
}
res.append("NULL");
return res.toString();
}
}
-
測(cè)試用例
public static void main(String[] args) {
MyLinkedList2 myLinkedList2 = new MyLinkedList2();
myLinkedList2.addAtHead(1);
System.out.println(myLinkedList2);
myLinkedList2.addAtTail(3);
System.out.println(myLinkedList2);
myLinkedList2.addAtIndex(1, 2);
System.out.println(myLinkedList2);
myLinkedList2.deleteAtIndex(1);
System.out.println(myLinkedList2);
myLinkedList2.get(1);
System.out.println(myLinkedList2);
}
-
結(jié)果
不知道測(cè)試用例是否有問題，一直無法通過leetcode中最后一個(gè)用例钠至。
-
源碼
-
我會(huì)隨時(shí)更新新的算法葛虐，并盡可能嘗試不同解法胎源，如果發(fā)現(xiàn)問題請(qǐng)指正
- Github
