1.題目描述
設(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)。如果index小于0塔淤，則在頭部插入節(jié)點(diǎn)摘昌。
deleteAtIndex(index)：如果索引 index 有效，則刪除鏈表中的第 index 個(gè)節(jié)點(diǎn)高蜂。
示例：
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
2.解題思路與代碼
2.1 解題思路
手寫雙向鏈表聪黎，自定義一個(gè) ListNode 類定義鏈表中的節(jié)點(diǎn)。ListNode 中定義了節(jié)點(diǎn)的值 val备恤，由于是雙向鏈表因此還需要定義該節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn) prev 和后續(xù)節(jié)點(diǎn) next挺举。
static class ListNode {
int val;
ListNode prev;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
定義好節(jié)點(diǎn)類后，便開始完成我們的鏈表類 MyLinkedList烘跺，因?yàn)樾枰迦腩^和尾節(jié)點(diǎn)湘纵，因此在 MyLinkedList 類中定義當(dāng)前鏈表的頭 head 和尾 tail，并且使用 size 統(tǒng)計(jì)當(dāng)前鏈表的節(jié)點(diǎn)個(gè)數(shù)滤淳。為了便于插入和刪除操作梧喷，我們?cè)诔跏蓟湵頃r(shí)定義虛擬頭節(jié)點(diǎn)和虛擬尾節(jié)點(diǎn)，并連接兩個(gè)節(jié)點(diǎn)脖咐。
public MyLinkedList() {
head = new ListNode(-1);
tail = new ListNode(-1);
head.next = tail;
tail.prev = head;
}
get(int index) 方法我們從 head 的 next 節(jié)點(diǎn)開始依次遍歷鏈表铺敌，直到遍歷到 index 個(gè)時(shí)，返回節(jié)點(diǎn)值即可屁擅。在遍歷之前我們需要判斷 index 是否小于 size偿凭，如果小于 size 直接返回，不再遍歷派歌。
public int get(int index) {
if (index >= size) {
return -1;
}
ListNode curr = head.next;
for (int i = 0; i < index; i++) {
curr = curr.next;
}
return curr.val;
}
addAtHead(int val) 方法直接在 head 和 head.next 之間添加值為 val 的新節(jié)點(diǎn)即可弯囊；同理 addAtTail(int val) 直接在 tail 和 tail.prev 之間添加值為 val 的新節(jié)點(diǎn)即可痰哨。
public void addAtHead(int val) {
ListNode listNode = new ListNode(val);
ListNode next = head.next;
head.next = listNode;
listNode.next = next;
next.prev = listNode;
listNode.prev = head;
size++;
}
public void addAtTail(int val) {
ListNode prev = tail.prev;
ListNode listNode = new ListNode(val);
prev.next = listNode;
listNode.next = tail;
tail.prev = listNode;
listNode.prev = prev;
size++;
}
addAtIndex(int index, int val) 方法需要在指定的位置出添加值為 val 的新節(jié)點(diǎn)，如果 index 大于 size匾嘱，即超過鏈表范圍斤斧，則不添加直接返回。index 如果小于 size霎烙，我們就從頭節(jié)點(diǎn) head 開始往后遍歷 index 個(gè)撬讽，由于 head 是虛擬頭節(jié)點(diǎn)，因此此時(shí)需要將新節(jié)點(diǎn)插入到 curr 和 curr.next 之間悬垃。
public void addAtIndex(int index, int val) {
if (index > size) {
return;
}
ListNode curr = head;
for (int i = 0; i < index; i++) {
curr = curr.next;
}
ListNode next = curr.next;
ListNode listNode = new ListNode(val);
curr.next = listNode;
listNode.next = next;
next.prev = listNode;
listNode.prev = curr;
size++;
}
deleteAtIndex(int index) 方法需要?jiǎng)h除 index 位置的節(jié)點(diǎn)游昼，同理如果 index 大于等于 size 超過鏈表范圍，則直接返回不刪除尝蠕。如果小于 size烘豌，首先還是從 head 開始往后遍歷 index 次，由于 head 是虛擬頭節(jié)點(diǎn)趟佃，此時(shí)我們只需要?jiǎng)h除 curr.next 這一個(gè)節(jié)點(diǎn)扇谣。
public void deleteAtIndex(int index) {
if (index >= size) {
return;
}
ListNode curr = head;
for (int i = 0; i < index; i++) {
curr = curr.next;
}
ListNode next = curr.next.next;
curr.next = next;
next.prev = curr;
size--;
}
2.2 代碼
class MyLinkedList {
MyLinkedList.ListNode head;
MyLinkedList.ListNode tail;
int size = 0;
public MyLinkedList() {
head = new MyLinkedList.ListNode(-1);
tail = new MyLinkedList.ListNode(-1);
head.next = tail;
tail.prev = head;
}
public int get(int index) {
if (index >= size) {
return -1;
}
MyLinkedList.ListNode curr = head.next;
for (int i = 0; i < index; i++) {
curr = curr.next;
}
return curr.val;
}
public void addAtHead(int val) {
MyLinkedList.ListNode listNode = new MyLinkedList.ListNode(val);
MyLinkedList.ListNode next = head.next;
head.next = listNode;
listNode.next = next;
next.prev = listNode;
listNode.prev = head;
size++;
}
public void addAtTail(int val) {
MyLinkedList.ListNode prev = tail.prev;
MyLinkedList.ListNode listNode = new MyLinkedList.ListNode(val);
prev.next = listNode;
listNode.next = tail;
tail.prev = listNode;
listNode.prev = prev;
size++;
}
public void addAtIndex(int index, int val) {
if (index > size) {
return;
}
MyLinkedList.ListNode curr = head;
for (int i = 0; i < index; i++) {
curr = curr.next;
}
MyLinkedList.ListNode next = curr.next;
MyLinkedList.ListNode listNode = new MyLinkedList.ListNode(val);
curr.next = listNode;
listNode.next = next;
next.prev = listNode;
listNode.prev = curr;
size++;
}
public void deleteAtIndex(int index) {
if (index >= size) {
return;
}
MyLinkedList.ListNode curr = head;
for (int i = 0; i < index; i++) {
curr = curr.next;
}
MyLinkedList.ListNode next = curr.next.next;
curr.next = next;
next.prev = curr;
size--;
}
static class ListNode {
int val;
MyLinkedList.ListNode prev;
MyLinkedList.ListNode next;
ListNode(int val) {
this.val = val;
}
}
}
2.3 測試結(jié)果
通過測試
3.總結(jié)
- 手寫一個(gè)雙向鏈表
- 在增加和刪除時(shí)需要注意鏈表大小和 index 的關(guān)系
