听说这道题目把链表常见的五个操作都覆盖了？
707.设计链表
题意：
在链表类中实现这些功能：
- get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
- addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
- addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
- addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
- deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
思路
如果对链表的基础知识还不太懂，可以看这篇文章：关于链表，你该了解这些！
如果对链表的虚拟头结点不清楚，可以看这篇文章：链表：听说用虚拟头节点会方便很多？
删除链表节点：
添加链表节点：
这道题目设计链表的五个接口：
- 获取链表第index个节点的数值
- 在链表的最前面插入一个节点
- 在链表的最后面插入一个节点
- 在链表第index个节点前面插入一个节点
- 删除链表的第index个节点
可以说这五个接口，已经覆盖了链表的常见操作，是练习链表操作非常好的一道题目
链表操作的两种方式：
- 直接使用原来的链表来进行操作。
- 设置一个虚拟头结点在进行操作。
下面采用的设置一个虚拟头结点（这样更方便一些，大家看代码就会感受出来）。
class MyLinkedList {
public:
// 定义链表节点结构体
struct LinkedNode {
int val;
LinkedNode* next;
LinkedNode(int val):val(val), next(nullptr){}
};
// 初始化链表
MyLinkedList() {
_dummyHead = new LinkedNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点
_size = 0;
}
// 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点
int get(int index) {
if (index > (_size - 1) || index < 0) {
return -1;
}
LinkedNode* cur = _dummyHead->next;
while(index--){ // 如果--index 就会陷入死循环
cur = cur->next;
}
return cur->val;
}
// 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点
void addAtHead(int val) {
LinkedNode* newNode = new LinkedNode(val);
newNode->next = _dummyHead->next;
_dummyHead->next = newNode;
_size++;
}
// 在链表最后面添加一个节点
void addAtTail(int val) {
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* cur = _dummyHead;
while(cur->next != nullptr){
cur = cur->next;
}
cur->next = newNode;
_size++;
}
// 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
// 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点
// 如果index大于链表的长度，则返回空
// 如果index小于0，则在头部插入节点
void addAtIndex(int index, int val) {
if(index > _size) return;
if(index < 0) index = 0;
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* cur = _dummyHead;
while(index--) {
cur = cur->next;
}
newNode->next = cur->next;
cur->next = newNode;
_size++;
}
// 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的
void deleteAtIndex(int index) {
if (index >= _size || index < 0) {
return;
}
LinkedNode* cur = _dummyHead;
while(index--) {
cur = cur ->next;
}
LinkedNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
//delete命令指示释放了tmp指针原本所指的那部分内存，
//被delete后的指针tmp的值（地址）并非就是NULL，而是随机值。也就是被delete后，
//如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针
//如果之后的程序不小心使用了tmp，会指向难以预想的内存空间
tmp=nullptr;
_size--;
}
// 打印链表
void printLinkedList() {
LinkedNode* cur = _dummyHead;
while (cur->next != nullptr) {
cout << cur->next->val << " ";
cur = cur->next;
}
cout << endl;
}
private:
int _size;
LinkedNode* _dummyHead;
};
- 时间复杂度: 涉及
index的相关操作为 O(index), 其余为 O(1) - 空间复杂度: O(n)
其他语言版本
C:
typedef struct MyLinkedList {
int val;
struct MyLinkedList* next;
}MyLinkedList;
/** Initialize your data structure here. */
MyLinkedList* myLinkedListCreate() {
//这个题必须用虚拟头指针,参数都是一级指针,头节点确定后没法改指向了!!!
MyLinkedList* head = (MyLinkedList *)malloc(sizeof (MyLinkedList));
head->next = NULL;
return head;
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
int myLinkedListGet(MyLinkedList* obj, int index) {
MyLinkedList *cur = obj->next;
for (int i = 0; cur != NULL; i++){
if (i == index){
return cur->val;
}
else{
cur = cur->next;
}
}
return -1;
}
/** 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. */
void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
MyLinkedList *nhead = (MyLinkedList *)malloc(sizeof (MyLinkedList));
nhead->val = val;
nhead->next = obj->next;
obj->next = nhead;
}
/** Append a node of value val to the last element of the linked list. */
void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
MyLinkedList *cur = obj;
while(cur->next != NULL){
cur = cur->next;
}
MyLinkedList *ntail = (MyLinkedList *)malloc(sizeof (MyLinkedList));
ntail->val = val;
ntail->next = NULL;
cur->next = ntail;
}
/** 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. */
void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
if (index == 0){
myLinkedListAddAtHead(obj, val);
return;
}
MyLinkedList *cur = obj->next;
for (int i = 1 ;cur != NULL; i++){
if (i == index){
MyLinkedList* newnode = (MyLinkedList *)malloc(sizeof (MyLinkedList));
newnode->val = val;
newnode->next = cur->next;
cur->next = newnode;
return;
}
else{
cur = cur->next;
}
}
}
/** Delete the index-th node in the linked list, if the index is valid. */
void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
if (index == 0){
MyLinkedList *tmp = obj->next;
if (tmp != NULL){
obj->next = tmp->next;
free(tmp);
}
return;
}
MyLinkedList *cur = obj->next;
for (int i = 1 ;cur != NULL && cur->next != NULL; i++){
if (i == index){
MyLinkedList *tmp = cur->next;
if (tmp != NULL) {
cur->next = tmp->next;
free(tmp);
}
return;
}
else{
cur = cur->next;
}
}
}
void myLinkedListFree(MyLinkedList* obj) {
while(obj != NULL){
MyLinkedList *tmp = obj;
obj = obj->next;
free(tmp);
}
}
/**
* Your MyLinkedList struct will be instantiated and called as such:
* MyLinkedList* obj = myLinkedListCreate();
* int param_1 = myLinkedListGet(obj, index);
* myLinkedListAddAtHead(obj, val);
* myLinkedListAddAtTail(obj, val);
* myLinkedListAddAtIndex(obj, index, val);
* myLinkedListDeleteAtIndex(obj, index);
* myLinkedListFree(obj);
*/
Java：
//单链表
class ListNode {
int val;
ListNode next;
ListNode(){}
ListNode(int val) {
this.val=val;
}
}
class MyLinkedList {
//size存储链表元素的个数
int size;
//虚拟头结点
ListNode head;
//初始化链表
public MyLinkedList() {
size = 0;
head = new ListNode(0);
}
//获取第index个节点的数值，注意index是从0开始的，第0个节点就是头结点
public int get(int index) {
//如果index非法，返回-1
if (index < 0 || index >= size) {
return -1;
}
ListNode currentNode = head;
//包含一个虚拟头节点，所以查找第 index+1 个节点
for (int i = 0; i <= index; i++) {
currentNode = currentNode.next;
}
return currentNode.val;
}
//在链表最前面插入一个节点，等价于在第0个元素前添加
public void addAtHead(int val) {
addAtIndex(0, val);
}
//在链表的最后插入一个节点，等价于在(末尾+1)个元素前添加
public void addAtTail(int val) {
addAtIndex(size, val);
}
// 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
// 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点
// 如果 index 大于链表的长度，则返回空
public void addAtIndex(int index, int val) {
if (index > size) {
return;
}
if (index < 0) {
index = 0;
}
size++;
//找到要插入节点的前驱
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个节点
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;
}
}
//双链表
class ListNode{
int val;
ListNode next,prev;
ListNode() {};
ListNode(int val){
this.val = val;
}
}
class MyLinkedList {
//记录链表中元素的数量
int size;
//记录链表的虚拟头结点和尾结点
ListNode head,tail;
public MyLinkedList() {
//初始化操作
this.size = 0;
this.head = new ListNode(0);
this.tail = new ListNode(0);
//这一步非常关键，否则在加入头结点的操作中会出现null.next的错误！！！
head.next=tail;
tail.prev=head;
}
public int get(int index) {
//判断index是否有效
if(index<0 || index>=size){
return -1;
}
ListNode cur = this.head;
//判断是哪一边遍历时间更短
if(index >= size / 2){
//tail开始
cur = tail;
for(int i=0; i< size-index; i++){
cur = cur.prev;
}
}else{
for(int i=0; i<= index; i++){
cur = cur.next;
}
}
return cur.val;
}
public void addAtHead(int val) {
//等价于在第0个元素前添加
addAtIndex(0,val);
}
public void addAtTail(int val) {
//等价于在最后一个元素(null)前添加
addAtIndex(size,val);
}
public void addAtIndex(int index, int val) {
//index大于链表长度
if(index>size){
return;
}
//index小于0
if(index<0){
index = 0;
}
size++;
//找到前驱
ListNode pre = this.head;
for(int i=0; i<index; i++){
pre = pre.next;
}
//新建结点
ListNode newNode = new ListNode(val);
newNode.next = pre.next;
pre.next.prev = newNode;
newNode.prev = pre;
pre.next = newNode;
}
public void deleteAtIndex(int index) {
//判断索引是否有效
if(index<0 || index>=size){
return;
}
//删除操作
size--;
ListNode pre = this.head;
for(int i=0; i<index; i++){
pre = pre.next;
}
pre.next.next.prev = pre;
pre.next = pre.next.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);
*/
Python：
（版本一）单链表法
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class MyLinkedList:
def __init__(self):
self.dummy_head = ListNode()
self.size = 0
def get(self, index: int) -> int:
if index < 0 or index >= self.size:
return -1
current = self.dummy_head.next
for i in range(index):
current = current.next
return current.val
def addAtHead(self, val: int) -> None:
self.dummy_head.next = ListNode(val, self.dummy_head.next)
self.size += 1
def addAtTail(self, val: int) -> None:
current = self.dummy_head
while current.next:
current = current.next
current.next = ListNode(val)
self.size += 1
def addAtIndex(self, index: int, val: int) -> None:
if index < 0 or index > self.size:
return
current = self.dummy_head
for i in range(index):
current = current.next
current.next = ListNode(val, current.next)
self.size += 1
def deleteAtIndex(self, index: int) -> None:
if index < 0 or index >= self.size:
return
current = self.dummy_head
for i in range(index):
current = current.next
current.next = current.next.next
self.size -= 1
# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)
（版本二）双链表法
class ListNode:
def __init__(self, val=0, prev=None, next=None):
self.val = val
self.prev = prev
self.next = next
class MyLinkedList:
def __init__(self):
self.head = None
self.tail = None
self.size = 0
def get(self, index: int) -> int:
if index < 0 or index >= self.size:
return -1
if index < self.size // 2:
current = self.head
for i in range(index):
current = current.next
else:
current = self.tail
for i in range(self.size - index - 1):
current = current.prev
return current.val
def addAtHead(self, val: int) -> None:
new_node = ListNode(val, None, self.head)
if self.head:
self.head.prev = new_node
else:
self.tail = new_node
self.head = new_node
self.size += 1
def addAtTail(self, val: int) -> None:
new_node = ListNode(val, self.tail, None)
if self.tail:
self.tail.next = new_node
else:
self.head = new_node
self.tail = new_node
self.size += 1
def addAtIndex(self, index: int, val: int) -> None:
if index < 0 or index > self.size:
return
if index == 0:
self.addAtHead(val)
elif index == self.size:
self.addAtTail(val)
else:
if index < self.size // 2:
current = self.head
for i in range(index - 1):
current = current.next
else:
current = self.tail
for i in range(self.size - index):
current = current.prev
new_node = ListNode(val, current, current.next)
current.next.prev = new_node
current.next = new_node
self.size += 1
def deleteAtIndex(self, index: int) -> None:
if index < 0 or index >= self.size:
return
if index == 0:
self.head = self.head.next
if self.head:
self.head.prev = None
else:
self.tail = None
elif index == self.size - 1:
self.tail = self.tail.prev
if self.tail:
self.tail.next = None
else:
self.head = None
else:
if index < self.size // 2:
current = self.head
for i in range(index):
current = current.next
else:
current = self.tail
for i in range(self.size - index - 1):
current = current.prev
current.prev.next = current.next
current.next.prev = current.prev
self.size -= 1
# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)
Go：
//单链表实现
package main
import (
"fmt"
)
type SingleNode struct {
Val int // 节点的值
Next *SingleNode // 下一个节点的指针
}
type MyLinkedList struct {
dummyHead *SingleNode // 虚拟头节点
Size int // 链表大小
}
func main() {
list := Constructor() // 初始化链表
list.AddAtHead(100) // 在头部添加元素
list.AddAtTail(242) // 在尾部添加元素
list.AddAtTail(777) // 在尾部添加元素
list.AddAtIndex(1, 99999) // 在指定位置添加元素
list.printLinkedList() // 打印链表
}
/** Initialize your data structure here. */
func Constructor() MyLinkedList {
newNode := &SingleNode{ // 创建新节点
-999,
nil,
}
return MyLinkedList{ // 返回链表
dummyHead: newNode,
Size: 0,
}
}
/** Get the value of the index-th node in the linked list. If the index is
invalid, return -1. */
func (this *MyLinkedList) Get(index int) int {
/*if this != nil || index < 0 || index > this.Size {
return -1
}*/
if this == nil || index < 0 || index >= this.Size { // 如果索引无效则返回-1
return -1
}
// 让cur等于真正头节点
cur := this.dummyHead.Next // 设置当前节点为真实头节点
for i := 0; i < index; i++ { // 遍历到索引所在的节点
cur = cur.Next
}
return cur.Val // 返回节点值
}
/** 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. */
func (this *MyLinkedList) AddAtHead(val int) {
// 以下两行代码可用一行代替
// newNode := new(SingleNode)
// newNode.Val = val
newNode := &SingleNode{Val: val} // 创建新节点
newNode.Next = this.dummyHead.Next // 新节点指向当前头节点
this.dummyHead.Next = newNode // 新节点变为头节点
this.Size++ // 链表大小增加1
}
/** Append a node of value val to the last element of the linked list. */
func (this *MyLinkedList) AddAtTail(val int) {
newNode := &SingleNode{Val: val} // 创建新节点
cur := this.dummyHead // 设置当前节点为虚拟头节点
for cur.Next != nil { // 遍历到最后一个节点
cur = cur.Next
}
cur.Next = newNode // 在尾部添加新节点
this.Size++ // 链表大小增加1
}
/** 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. */
func (this *MyLinkedList) AddAtIndex(index int, val int) {
if index < 0 { // 如果索引小于0，设置为0
index = 0
} else if index > this.Size { // 如果索引大于链表长度，直接返回
return
}
newNode := &SingleNode{Val: val} // 创建新节点
cur := this.dummyHead // 设置当前节点为虚拟头节点
for i := 0; i < index; i++ { // 遍历到指定索引的前一个节点
cur = cur.Next
}
newNode.Next = cur.Next // 新节点指向原索引节点
cur.Next = newNode // 原索引的前一个节点指向新节点
this.Size++ // 链表大小增加1
}
/** Delete the index-th node in the linked list, if the index is valid. */
func (this *MyLinkedList) DeleteAtIndex(index int) {
if index < 0 || index >= this.Size { // 如果索引无效则直接返回
return
}
cur := this.dummyHead // 设置当前节点为虚拟头节点
for i := 0; i < index; i++ { // 遍历到要删除节点的前一个节点
cur = cur.Next
}
if cur.Next != nil {
cur.Next = cur.Next.Next // 当前节点直接指向下下个节点，即删除了下一个节点
}
this.Size-- // 注意删除节点后应将链表大小减一
}
// 打印链表
func (list *MyLinkedList) printLinkedList() {
cur := list.dummyHead // 设置当前节点为虚拟头节点
for cur.Next != nil { // 遍历链表
fmt.Println(cur.Next.Val) // 打印节点值
cur = cur.Next // 切换到下一个节点
}
}
//循环双链表
type MyLinkedList struct {
dummy *Node
}
type Node struct {
Val int
Next *Node
Pre *Node
}
//仅保存哑节点，pre-> rear, next-> head
/** Initialize your data structure here. */
func Constructor() MyLinkedList {
rear := &Node{
Val: -1,
Next: nil,
Pre: nil,
}
rear.Next = rear
rear.Pre = rear
return MyLinkedList{rear}
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
func (this *MyLinkedList) Get(index int) int {
head := this.dummy.Next
//head == this, 遍历完全
for head != this.dummy && index > 0 {
index--
head = head.Next
}
//否则, head == this, 索引无效
if 0 != index {
return -1
}
return head.Val
}
/** 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. */
func (this *MyLinkedList) AddAtHead(val int) {
dummy := this.dummy
node := &Node{
Val: val,
//head.Next指向原头节点
Next: dummy.Next,
//head.Pre 指向哑节点
Pre: dummy,
}
//更新原头节点
dummy.Next.Pre = node
//更新哑节点
dummy.Next = node
//以上两步不能反
}
/** Append a node of value val to the last element of the linked list. */
func (this *MyLinkedList) AddAtTail(val int) {
dummy := this.dummy
rear := &Node{
Val: val,
//rear.Next = dummy(哑节点)
Next: dummy,
//rear.Pre = ori_rear
Pre: dummy.Pre,
}
//ori_rear.Next = rear
dummy.Pre.Next = rear
//update dummy
dummy.Pre = rear
//以上两步不能反
}
/** 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. */
func (this *MyLinkedList) AddAtIndex(index int, val int) {
head := this.dummy.Next
//head = MyLinkedList[index]
for head != this.dummy && index > 0 {
head = head.Next
index--
}
if index > 0 {
return
}
node := &Node{
Val: val,
//node.Next = MyLinkedList[index]
Next: head,
//node.Pre = MyLinkedList[index-1]
Pre: head.Pre,
}
//MyLinkedList[index-1].Next = node
head.Pre.Next = node
//MyLinkedList[index].Pre = node
head.Pre = node
//以上两步不能反
}
/** Delete the index-th node in the linked list, if the index is valid. */
func (this *MyLinkedList) DeleteAtIndex(index int) {
//链表为空
if this.dummy.Next == this.dummy {
return
}
head := this.dummy.Next
//head = MyLinkedList[index]
for head.Next != this.dummy && index > 0 {
head = head.Next
index--
}
//验证index有效
if index == 0 {
//MyLinkedList[index].Pre = index[index-2]
head.Next.Pre = head.Pre
//MyLinedList[index-2].Next = index[index]
head.Pre.Next = head.Next
//以上两步顺序无所谓
}
}
JavaScript:
class LinkNode {
constructor(val, next) {
this.val = val;
this.next = next;
}
}
/**
* Initialize your data structure here.
* 单链表 储存头尾节点 和 节点数量
*/
var MyLinkedList = function() {
this._size = 0;
this._tail = null;
this._head = null;
};
/**
* Get the value of the index-th node in the linked list. If the index is invalid, return -1.
* @param {number} index
* @return {number}
*/
MyLinkedList.prototype.getNode = function(index) {
if(index < 0 || index >= this._size) return null;
// 创建虚拟头节点
let cur = new LinkNode(0, this._head);
// 0 -> head
while(index-- >= 0) {
cur = cur.next;
}
return cur;
};
MyLinkedList.prototype.get = function(index) {
if(index < 0 || index >= this._size) return -1;
// 获取当前节点
return this.getNode(index).val;
};
/**
* 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.
* @param {number} val
* @return {void}
*/
MyLinkedList.prototype.addAtHead = function(val) {
const node = new LinkNode(val, this._head);
this._head = node;
this._size++;
if(!this._tail) {
this._tail = node;
}
};
/**
* Append a node of value val to the last element of the linked list.
* @param {number} val
* @return {void}
*/
MyLinkedList.prototype.addAtTail = function(val) {
const node = new LinkNode(val, null);
this._size++;
if(this._tail) {
this._tail.next = node;
this._tail = node;
return;
}
this._tail = node;
this._head = node;
};
/**
* 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.
* @param {number} index
* @param {number} val
* @return {void}
*/
MyLinkedList.prototype.addAtIndex = function(index, val) {
if(index > this._size) return;
if(index <= 0) {
this.addAtHead(val);
return;
}
if(index === this._size) {
this.addAtTail(val);
return;
}
// 获取目标节点的上一个的节点
const node = this.getNode(index - 1);
node.next = new LinkNode(val, node.next);
this._size++;
};
/**
* Delete the index-th node in the linked list, if the index is valid.
* @param {number} index
* @return {void}
*/
MyLinkedList.prototype.deleteAtIndex = function(index) {
if(index < 0 || index >= this._size) return;
if(index === 0) {
this._head = this._head.next;
// 如果删除的这个节点同时是尾节点，要处理尾节点
if(index === this._size - 1){
this._tail = this._head
}
this._size--;
return;
}
// 获取目标节点的上一个的节点
const node = this.getNode(index - 1);
node.next = node.next.next;
// 处理尾节点
if(index === this._size - 1) {
this._tail = node;
}
this._size--;
};
// MyLinkedList.prototype.out = function() {
// let cur = this._head;
// const res = [];
// while(cur) {
// res.push(cur.val);
// cur = cur.next;
// }
// };
/**
* Your MyLinkedList object will be instantiated and called as such:
* var obj = new MyLinkedList()
* var param_1 = obj.get(index)
* obj.addAtHead(val)
* obj.addAtTail(val)
* obj.addAtIndex(index,val)
* obj.deleteAtIndex(index)
*/
TypeScript:
class ListNode {
public val: number;
public next: ListNode | null;
constructor(val?: number, next?: ListNode | null) {
this.val = val === undefined ? 0 : val;
this.next = next === undefined ? null : next;
}
}
class MyLinkedList {
// 记录链表长度
private size: number;
private head: ListNode | null;
private tail: ListNode | null;
constructor() {
this.size = 0;
this.head = null;
this.tail = null;
}
// 获取链表中第 index个节点的值
get(index: number): number {
// 索引无效的情况
if (index < 0 || index >= this.size) {
return -1;
}
let curNode = this.getNode(index);
// 这里在前置条件下，理论上不会出现 null的情况
return curNode.val;
}
// 在链表的第一个元素之前添加一个值为 val的节点。插入后，新节点将成为链表的第一个节点。
addAtHead(val: number): void {
let node: ListNode = new ListNode(val, this.head);
this.head = node;
if (!this.tail) {
this.tail = node;
}
this.size++;
}
// 将值为 val 的节点追加到链表的最后一个元素。
addAtTail(val: number): void {
let node: ListNode = new ListNode(val, null);
if (this.tail) {
this.tail.next = node;
} else {
// 还没有尾节点，说明一个节点都还没有
this.head = node;
}
this.tail = node;
this.size++;
}
// 在链表中的第 index个节点之前添加值为 val的节点。
// 如果 index等于链表的长度，则该节点将附加到链表的末尾。如果 index大于链表长度，则不会插入节点。如果 index小于0，则在头部插入节点。
addAtIndex(index: number, val: number): void {
if (index === this.size) {
this.addAtTail(val);
return;
}
if (index > this.size) {
return;
}
// <= 0 的情况都是在头部插入
if (index <= 0) {
this.addAtHead(val);
return;
}
// 正常情况
// 获取插入位置的前一个 node
let curNode = this.getNode(index - 1);
let node: ListNode = new ListNode(val, curNode.next);
curNode.next = node;
this.size++;
}
// 如果索引 index有效，则删除链表中的第 index个节点。
deleteAtIndex(index: number): void {
if (index < 0 || index >= this.size) {
return;
}
// 处理头节点
if (index === 0) {
this.head = this.head!.next;
// 如果链表中只有一个元素，删除头节点后，需要处理尾节点
if (index === this.size - 1) {
this.tail = null
}
this.size--;
return;
}
// 索引有效
let curNode: ListNode = this.getNode(index - 1);
curNode.next = curNode.next!.next;
// 处理尾节点
if (index === this.size - 1) {
this.tail = curNode;
}
this.size--;
}
// 获取指定 Node节点
private getNode(index: number): ListNode {
// 这里不存在没办法获取到节点的情况，都已经在前置方法做过判断
// 创建虚拟头节点
let curNode: ListNode = new ListNode(0, this.head);
for (let i = 0; i <= index; i++) {
// 理论上不会出现 null
curNode = curNode.next!;
}
return curNode;
}
}
Kotlin:
class MyLinkedList {
var next: ListNode? = null
var size: Int = 0
fun get(index: Int): Int {
if (index + 1 > size) return -1
var cur = this.next
for (i in 0 until index) {
cur = cur?.next
}
return cur?.`val` ?: -1
}
fun addAtHead(`val`: Int) {
val head = ListNode(`val`)
head.next = this.next
this.next = head
size++
}
fun addAtTail(`val`: Int) {
val pre = ListNode(0)
pre.next = this.next
var cur: ListNode? = pre
while (cur?.next != null) {
cur = cur.next
}
cur?.next = ListNode(`val`)
this.next = pre.next
size++
}
fun addAtIndex(index: Int, `val`: Int) {
if (index > size) return
val pre = ListNode(0)
pre.next = this.next
var cur:ListNode? = pre
for (i in 0 until index) {
cur = cur?.next
}
val temp = cur?.next
cur?.next = ListNode(`val`)
cur?.next?.next = temp
this.next = pre.next
size++
}
fun deleteAtIndex(index: Int) {
if (index + 1 > size) return
val pre = ListNode(0)
pre.next = this.next
var cur: ListNode? = pre
for (i in 0 until index) {
cur = cur?.next
}
val temp = cur?.next?.next
cur?.next?.next = null
cur?.next = temp
this.next = pre.next
size--
}
}
Swift:
class MyLinkedList {
var dummyHead: ListNode<Int>?
var size: Int
init() {
dummyHead = ListNode(0)
size = 0
}
func get(_ index: Int) -> Int {
if index >= size || index < 0 {
return -1
}
var curNode = dummyHead?.next
var curIndex = index
while curIndex > 0 {
curNode = curNode?.next
curIndex -= 1
}
return curNode?.value ?? -1
}
func addAtHead(_ val: Int) {
let newHead = ListNode(val)
newHead.next = dummyHead?.next
dummyHead?.next = newHead
size += 1
}
func addAtTail(_ val: Int) {
let newNode = ListNode(val)
var curNode = dummyHead
while curNode?.next != nil {
curNode = curNode?.next
}
curNode?.next = newNode
size += 1
}
func addAtIndex(_ index: Int, _ val: Int) {
if index > size {
return
}
let newNode = ListNode(val)
var curNode = dummyHead
var curIndex = index
while curIndex > 0 {
curNode = curNode?.next
curIndex -= 1
}
newNode.next = curNode?.next
curNode?.next = newNode
size += 1
}
func deleteAtIndex(_ index: Int) {
if index >= size || index < 0 {
return
}
var curNode = dummyHead
for _ in 0..<index {
curNode = curNode?.next
}
curNode?.next = curNode?.next?.next
size -= 1
}
}
Scala:
class ListNode(_x: Int = 0, _next: ListNode = null) {
var next: ListNode = _next
var x: Int = _x
}
class MyLinkedList() {
var size = 0 // 链表尺寸
var dummy: ListNode = new ListNode(0) // 虚拟头节点
// 获取第index个节点的值
def get(index: Int): Int = {
if (index < 0 || index >= size) {
return -1;
}
var cur = dummy
for (i <- 0 to index) {
cur = cur.next
}
cur.x // 返回cur的值
}
// 在链表最前面插入一个节点
def addAtHead(`val`: Int) {
addAtIndex(0, `val`)
}
// 在链表最后面插入一个节点
def addAtTail(`val`: Int) {
addAtIndex(size, `val`)
}
// 在第index个节点之前插入一个新节点
// 如果index等于链表长度，则说明新插入的节点是尾巴
// 如果index等于0，则说明新插入的节点是头
// 如果index>链表长度，则说明为空
def addAtIndex(index: Int, `val`: Int) {
if (index > size) {
return
}
var loc = index // 因为参数index是val不可变类型，所以需要赋值给一个可变类型
if (index < 0) {
loc = 0
}
size += 1 //链表尺寸+1
var pre = dummy
for (i <- 0 until loc) {
pre = pre.next
}
val node: ListNode = new ListNode(`val`, pre.next)
pre.next = node
}
// 删除第index个节点
def deleteAtIndex(index: Int) {
if (index < 0 || index >= size) {
return
}
size -= 1
var pre = dummy
for (i <- 0 until index) {
pre = pre.next
}
pre.next = pre.next.next
}
}
Rust:
#[derive(Debug)]
pub struct MyLinkedList {
pub val: i32,
pub next: Option<Box<MyLinkedList>>,
}
impl MyLinkedList {
fn new() -> Self {
// 增加头节点
MyLinkedList { val: 0, next: None }
}
fn get(&self, index: i32) -> i32 {
if index < 0 {
return -1;
}
let mut i = 0;
let mut cur = &self.next;
while let Some(node) = cur {
if i == index {
return node.val;
}
i += 1;
cur = &node.next;
}
-1
}
fn add_at_head(&mut self, val: i32) {
let new_node = Box::new(MyLinkedList {
val,
next: self.next.take(),
});
self.next = Some(new_node);
}
fn add_at_tail(&mut self, val: i32) {
let new_node = Box::new(MyLinkedList { val, next: None });
let mut last_node = &mut self.next;
while let Some(node) = last_node {
last_node = &mut node.next;
}
*last_node = Some(new_node);
}
fn add_at_index(&mut self, index: i32, val: i32) {
if index <= 0 {
self.add_at_head(val);
} else {
let mut i = 0;
let mut cur = &mut self.next;
while let Some(node) = cur {
if i + 1 == index {
let new_node = Box::new(MyLinkedList {
val,
next: node.next.take(),
});
node.next = Some(new_node);
break;
}
i += 1;
cur = &mut node.next;
}
}
}
fn delete_at_index(&mut self, index: i32) {
if index < 0 {
return;
}
let mut i = 0;
let mut cur = self;
while let Some(node) = cur.next.take() {
if i == index {
cur.next = node.next;
break;
}
i += 1;
cur.next = Some(node);
cur = cur.next.as_mut().unwrap();
}
}
}
C#
class ListNode
{
public int val;
public ListNode next;
public ListNode(int val) { this.val = val; }
}
public class MyLinkedList
{
ListNode dummyHead;
int count;
public MyLinkedList()
{
dummyHead = new ListNode(0);
count = 0;
}
public int Get(int index)
{
if (index < 0 || count <= index) return -1;
ListNode current = dummyHead;
for (int i = 0; i <= index; i++)
{
current = current.next;
}
return current.val;
}
public void AddAtHead(int val)
{
AddAtIndex(0, val);
}
public void AddAtTail(int val)
{
AddAtIndex(count, val);
}
public void AddAtIndex(int index, int val)
{
if (index > count) return;
index = Math.Max(0, index);
count++;
ListNode tmp1 = dummyHead;
for (int i = 0; i < index; i++)
{
tmp1 = tmp1.next;
}
ListNode tmp2 = new ListNode(val);
tmp2.next = tmp1.next;
tmp1.next = tmp2;
}
public void DeleteAtIndex(int index)
{
if (index >= count || index < 0) return;
var tmp1 = dummyHead;
for (int i = 0; i < index; i++)
{
tmp1 = tmp1.next;
}
tmp1.next = tmp1.next.next;
count--;
}
}