题目描述
设计链表
思路
单链表
根据题意，可以选择单链表和双链表解题，先使用单链表。
因为使用单链表，即每个节点只存储值和直接后继节点，还需要一个哨兵节点（sentinel node）作为头节点，和一个size参数保存有效节点数。
初始化时，只需创建头节点head和size即可。
实现get(index)时，先判断有效性，再通过循环找到对应节点的值。
实现addAtIndex(index, val)时，如果index是有效值，则需要找到原来下标为index的节点的直接前驱结点pred，并创建新节点cur，将cur的直接后继节点设为pred的直接后继节点，将pred的直接后继节点设为cur，更新size，这样的操作对于index=0也成立。
实现addAtHead(val)和addAtTail(val)，可以借助addAtIndex(index, val)实现。
实现deleteAtIndex(index)时，需要先判断index是有效值。然后找到下标为index的节点的直接前驱节点pred，通过将pred的直接后继节点更新为pred的直接后继节点的直接后继节点，来大城删除节点的效果，同时更新size。
Python实现
class ListNode:
def __init__(self, val):
self.val = val
self.next = None
class MyLinkedList:
def __init__(self):
self.size = 0
self.head = ListNode(0)
def get(self, index: int) -> int:
if index < 0 or index >= self.size:
return -1
cur = self.head
for i in range(index + 1):
cur = cur.next
return cur.val
def addAtHead(self, val: int) -> None:
self.addAtIndex(0, val)
def addAtTail(self, val: int) -> None:
self.addAtIndex(self.size, val)
def addAtIndex(self, index: int, val: int) -> None:
if index > self.size:
return
index = max(0, index)
self.size += 1
pred = self.head
for i in range(index):
pred = pred.next
cur = ListNode(val)
cur.next = pred.next
pred.next = cur
def deleteAtIndex(self, index: int) -> None:
if index < 0 or index >= self.size:
return
self.size -= 1
pred = self.head
for i in range(index):
pred = pred.next
pred.next = pred.next.next
Java实现
class ListNode {
int val;
ListNode next;
public 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 cur = head;
for (int i = 0; i <= index; i++) {
cur = cur.next;
}
return cur.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;
}
index = Math.max(0, index);
size++;
ListNode pred = head;
for (int i = 0; i < index; i++) {
pred = pred.next;
}
ListNode cur = new ListNode(val);
cur.next = pred.next;
pred.next = cur;
}
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) {
return;
}
size--;
ListNode pred = head;
for (int i = 0; i < index; i++) {
pred = pred.next;
}
pred.next = pred.next.next;
}
}
C++实现
class MyLinkedList {
private:
int size;
ListNode *head;
public:
MyLinkedList() {
this -> size = 0;
this->head = new ListNode(0);
}
int get(int index) {
if (index < 0 || index >= size) {
return -1;
}
ListNode *cur = head;
for (int i = 0; i <= index; i++) {
cur = cur->next;
}
return cur->val;
}
void addAtHead(int val) {
addAtIndex(0, val);
}
void addAtTail(int val) {
addAtIndex(size, val);
}
void addAtIndex(int index, int val) {
if (index > size) {
return;
}
index = max(0, index);
size++;
ListNode *pred = head;
for (int i = 0; i < index; i++) {
pred = pred->next;
}
ListNode *cur = new ListNode(val);
cur->next = pred->next;
pred->next = cur;
}
void deleteAtIndex(int index) {
if (index < 0 || index >= size) {
return;
}
size--;
ListNode *pred = head;
for (int i = 0; i < index; i++) {
pred = pred->next;
}
ListNode *cur = pred->next;
pred->next = pred->next->next;
delete cur;
}
};
双链表
题目给定的另一种方法是双链表，实际上就是每个节点多存储一个直接前驱节点，除此之外，哨兵节点共需要两个，分别为头节点和尾节点，还需要一个size计算有效节点数。
初始化时，创建头节点和size即可。
实现get(index)时，先判断有效性，比较看是从head开始还是从tail开始遍历会更快找到目标，然后开始遍历。
实现addAtIndex(index, val)时，如果index是有效值，则找到原来下标为index的节点next和其直接前驱节点pred，并创建新节点cur，再对pred和next节点变量地更新来插入节点cur，最后更新size。
addAtHead(val)和addAtTail(val)都可以通过addAtIndex(index, val)来实现。
实现deleteAtIndex(index)时，先判断index有效性，然后找到下标为index的节点cur和其直接前驱节点pred和直接后继节点next，再对pred和next的变量进行修改来删除节点，最后更新size。
Python实现
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
self.prev = None
class MyLinkedList:
def __init__(self):
self.size = 0
self.head, self.tail = ListNode(0), ListNode(0)
self.head.next = self.tail
self.tail.prev = self.head
def get(self, index: int) -> int:
if index < 0 or index >= self.size:
return -1
if index + 1 < self.size - index:
curr = self.head
for _ in range(index + 1):
curr = curr.next
else:
curr = self.tail
for _ in range(self.size - index):
curr = curr.prev
return curr.val
def addAtHead(self, val: int) -> None:
self.addAtIndex(0, val)
def addAtTail(self, val: int) -> None:
self.addAtIndex(self.size, val)
def addAtIndex(self, index: int, val: int) -> None:
if index > self.size:
return
index = max(0, index)
if index < self.size - index:
pred = self.head
for _ in range(index):
pred = pred.next
succ = pred.next
else:
succ = self.tail
for _ in range(self.size - index):
succ = succ.prev
pred = succ.prev
self.size += 1
to_add = ListNode(val)
to_add.prev = pred
to_add.next = succ
pred.next = to_add
succ.prev = to_add
def deleteAtIndex(self, index: int) -> None:
if index < 0 or index >= self.size:
return
if index < self.size - index:
pred = self.head
for _ in range(index):
pred = pred.next
succ = pred.next.next
else:
succ = self.tail
for _ in range(self.size - index - 1):
succ = succ.prev
pred = succ.prev.prev
self.size -= 1
pred.next = succ
succ.prev = pred
其他两种语言类似，不再赘述。
|