題目
設(shè)計鏈表的實現(xiàn)。您可以選擇使用單鏈表或雙鏈表。單鏈表中的節(jié)點應(yīng)該具有兩個屬性：val 和 next莹桅。val 是當(dāng)前節(jié)點的值，next 是指向下一個節(jié)點的指針/引用固棚。如果要使用雙向鏈表统翩，則還需要一個屬性 prev 以指示鏈表中的上一個節(jié)點。假設(shè)鏈表中的所有節(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é)點沮峡。
示例：
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
提示：
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/design-linked-list
我的解
class Node{
public int val;
public Node next;
public Node(){
}
public Node(int val){
this.val = val;
this.next = null;
}
public Node(int val, Node next){
this.val = val;
this.next = next;
}
}
class MyLinkedList {
public Node head;
public MyLinkedList() {
this.head = null;
}
public int get(int index) {
if(this.head == null){
return -1;
}
Node cur = this.head;//定義一個遍歷鏈表得指針
int count = 0;//定義一個記錄當(dāng)前index得變量
while(count != index){
if(cur.next == null){
return -1;
}
cur = cur.next;
count++;
}
return cur.val;
}
public void addAtHead(int val) {
Node newHead = new Node(val);
if(this.head == null){
this.head = newHead;
}else{
newHead.next = this.head;
this.head = newHead;
}
}
public void addAtTail(int val) {
Node newTail = new Node(val);
if(this.head == null){
this.head = newTail;
}else{
Node cur = this.head;
while(cur.next != null){
cur = cur.next;
}
cur.next = newTail;//找到了最后一個節(jié)，把新節(jié)點加上去
}
}
public void addAtIndex(int index, int val) {
if(this.head == null && index > 0){
return;
}else {
Node nodeIndex = new Node(val);
Node fakeNode = new Node(0,this.head);
Node cur = fakeNode;//定義一個遍歷鏈表得指針
int count = -1;//定義一個記錄當(dāng)前index得變量
while((count + 1) != index){
if(cur.next == null){
return;
}
cur = cur.next;
count++;
}
nodeIndex.next = cur.next;
cur.next = nodeIndex;
this.head = fakeNode.next;
}
}
public void deleteAtIndex(int index) {
if(this.head == null){
return;
}
Node fakeNode = new Node(0,this.head);
Node cur = fakeNode;//定義一個遍歷鏈表得指針
int count = -1;//定義一個記錄當(dāng)前index得變量
while((count + 1) != index){
if(cur.next == null){
return;
}
cur = cur.next;
count++;
}
if(cur.next == null){
return;
}
cur.next = cur.next.next;
this.head = fakeNode.next;
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList obj = new MyLinkedList();
* int param_1 = obj.get(index);
* obj.addAtHead(val);
* obj.addAtTail(val);
* obj.addAtIndex(index,val);
* obj.deleteAtIndex(index);
*/
代碼隨想錄的解
//單鏈表
class ListNode {
int val;
ListNode next;
ListNode(){}
ListNode(int val) {
this.val=val;
}
}
class MyLinkedList {
//size存儲鏈表元素的個數(shù)
int size;
//虛擬頭結(jié)點
ListNode head;
//初始化鏈表
public MyLinkedList() {
size = 0;
head = new ListNode(0);
}
//獲取第index個節(jié)點的數(shù)值亿柑，注意index是從0開始的邢疙，第0個節(jié)點就是頭結(jié)點
public int get(int index) {
//如果index非法，返回-1
if (index < 0 || index >= size) {
return -1;
}
ListNode currentNode = head;
//包含一個虛擬頭節(jié)點，所以查找第 index+1 個節(jié)點
for (int i = 0; i <= index; i++) {
currentNode = currentNode.next;
}
return currentNode.val;
}
//在鏈表最前面插入一個節(jié)點疟游，等價于在第0個元素前添加
public void addAtHead(int val) {
addAtIndex(0, val);
}
//在鏈表的最后插入一個節(jié)點呼畸，等價于在(末尾+1)個元素前添加
public void addAtTail(int val) {
addAtIndex(size, val);
}
// 在第 index 個節(jié)點之前插入一個新節(jié)點，例如index為0乡摹，那么新插入的節(jié)點為鏈表的新頭節(jié)點役耕。
// 如果 index 等于鏈表的長度，則說明是新插入的節(jié)點為鏈表的尾結(jié)點
// 如果 index 大于鏈表的長度聪廉，則返回空
public void addAtIndex(int index, int val) {
if (index > size) {
return;
}
if (index < 0) {
index = 0;
}
size++;
//找到要插入節(jié)點的前驅(qū)
ListNode pred = head;
for (int i = 0; i < index; i++) {
pred = pred.next;
}
ListNode toAdd = new ListNode(val);
toAdd.next = pred.next;
pred.next = toAdd;
}
//刪除第index個節(jié)點
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) {
return;
}
size--;
if (index == 0) {
head = head.next;
return;
}
ListNode pred = head;
for (int i = 0; i < index ; i++) {
pred = pred.next;
}
pred.next = pred.next.next;
}
}
收獲
1.標(biāo)準的單鏈表具有size和虛擬頭節(jié)點屬性，虛擬頭節(jié)點意味著此頭節(jié)點并不存放用戶數(shù)據(jù)故慈，是為了簡化過程板熊，size大小中不包含此虛擬頭節(jié)點。
2.增加和刪除操作中察绷，一定是需要操作的節(jié)點的前驅(qū)節(jié)點在移動干签。
