题目
设计链表的实现。可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。
val是当前节点的值next是指向下一个节点的指针/引用。
如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。
假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
示例：
MyLinkedList linkedList = new MyLinkedList();linkedList.addAtHead(1);linkedList.addAtTail(3);linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3linkedList.get(1); //返回2linkedList.deleteAtIndex(1); //现在链表是1-> 3linkedList.get(1); //返回3
提示：
- 所有val值都在
[1, 1000]之内。 - 操作次数将在
[1, 1000]之内。 - 请不要使用内置的
LinkedList库。
方案一（单链表）
python 版
class Node:
def __init__(self, val, next_=None):
self.val = val
self.next = next_
class Tail:
def __init__(self):
pass
class MyLinkedList:
def __init__(self):
"""
Initialize your data structure here.
"""
self._head = None
self._tail = Tail()
self._count = 0 # 链表中元素的个数
def get(self, index: int) -> int:
"""
Get the value of the index-th node in the linked list. If the index is invalid, return -1.
"""
return self._get(index)[1]
def _get(self, index):
if index >= self._count:
return None, -1
node = self._head
for _ in range(index):
node = node.next
return node, node.val
def addAtHead(self, val: int) -> None:
"""
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.
"""
if self._count == 0:
self._head = Node(val, self._tail)
else:
node = Node(val, self._head)
self._head = node
self._count += 1
def addAtTail(self, val: int) -> None:
"""
Append a node of value val to the last element of the linked list.
"""
if self._count == 0:
self._head = Node(val, self._tail)
else:
node = Node(val, self._tail)
prev, _ = self._get(self._count - 1)
prev.next = node
self._count += 1
def addAtIndex(self, index: int, val: int) -> None:
"""
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.
"""
if index == 0:
self.addAtHead(val)
elif index == self._count:
self.addAtTail(val)
elif index < self._count:
prev, _ = self._get(index - 1)
next_ = prev.next
prev.next = Node(val, next_)
self._count += 1
else:
return
def deleteAtIndex(self, index: int) -> None:
"""
Delete the index-th node in the linked list, if the index is valid.
"""
if index >= self._count:
return None
elif index == 0: # 删除第一个节点
self._head, _ = self._get(1)
elif index == self._count - 1: # 删除最后一个节点
self._tail, _ = self._get(index - 1)
else:
prev, _ = self._get(index - 1)
next_ = prev.next.next
prev.next = next_
self._count -= 1
def print_all(self):
print(f'count={self._count}')
node = self._head
while not isinstance(node, Tail):
print(f'{str(node.val)}-->')
node = node.next
- 上述方案插入节点的时间复杂度为
完全没有体现出链表的优势。
Go 语言版
type Node struct {
val int
next *Node
}
type MyLinkedList struct {
head *Node
tail *Node
length int
}
/** Initialize your data structure here. */
func Constructor() MyLinkedList {
linkedList := MyLinkedList{
tail: &Node{},
length: 0,
}
return linkedList
}
/** 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 index >= this.length {
return -1
}
node := this.head
for i := 0; i < index; i += 1 {
node = node.next
}
return node.val
}
func (this *MyLinkedList) get(index int) *Node {
node := this.head
for i := 0; i < index; i += 1 {
node = node.next
}
return node
}
/** 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) {
node := &Node{
val: val,
next: this.head,
}
this.head = node
this.length += 1
}
/** Append a node of value val to the last element of the linked list. */
func (this *MyLinkedList) AddAtTail(val int) {
prev := this.get(this.length - 1)
node := &Node{
val: val,
next: &Node{},
}
prev.next = node
this.length += 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 {
this.AddAtHead(val)
} else if index == this.length {
this.AddAtTail(val)
} else if index > 0 && index < this.length {
prev := this.get(index - 1)
next := prev.next
node := &Node{
val: val,
next: next,
}
prev.next = node
this.length += 1
}
}
/** Delete the index-th node in the linked list, if the index is valid. */
func (this *MyLinkedList) DeleteAtIndex(index int) {
if index >= this.length || index < 0 {
return
} else if index == 0 {
this.head = this.head.next
} else if index == this.length - 1 {
this.tail = this.get(index - 1)
} else {
prev := this.get(index - 1)
next := prev.next.next
prev.next = next
}
this.length -= 1
}
- 单链表在结构里有
tail节点意义不大
方案二（双链表）
type Node struct {
Val int
Prev *Node
Next *Node
}
type MyLinkedList struct {
head *Node
tail *Node
length int
}
/** Initialize your data structure here. */
func Constructor() MyLinkedList {
return MyLinkedList{
length: 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 index < 0 || index >= this.length {
return -1
}
node := this.getNode(index)
return node.Val
}
func (this *MyLinkedList) getNode(index int) *Node {
var node *Node
if index < this.length / 2 {
node = this.head
for i := 0; i < index; i++ {
node = node.Next
}
} else {
node = this.tail
for i := this.length - 1; i > index; i-- {
node = node.Prev
}
}
return node
}
/** 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) {
if this.length == 0 {
this.head = &Node {
Val: val,
}
this.tail = this.head
} else {
node := &Node {
Val: val,
Next: this.head,
}
this.head.Prev = node
this.head = node
}
this.length += 1
}
/** Append a node of value val to the last element of the linked list. */
func (this *MyLinkedList) AddAtTail(val int) {
if this.length == 0 {
this.AddAtHead(val)
} else {
node := &Node {
Val: val,
Prev: this.tail,
}
this.tail.Next = node
this.tail = node
this.length += 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 > this.length || index < 0 {
return
} else if index == this.length {
this.AddAtTail(val)
} else if index == 0 {
this.AddAtHead(val)
} else {
node := this.getNode(index)
newNode := &Node {
Val: val,
Prev: node.Prev,
Next: node,
}
node.Prev.Next = newNode
node.Prev = newNode
this.length += 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.length {
return
}
if index == 0 { // 删除头结点
this.head = this.head.Next
} else if index == this.length - 1 {
this.tail = this.tail.Prev
} else {
node := this.getNode(index)
node.Prev.Next = node.Next
node.Next.Prev = node.Prev
}
this.length -= 1
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Get(index);
* obj.AddAtHead(val);
* obj.AddAtTail(val);
* obj.AddAtIndex(index,val);
* obj.DeleteAtIndex(index);
*/
- 双链表在结构里包含一个
tail节点还是有些意义的；比如删除尾节点，在链表后半部获取插入等操作可以降低时间复杂度到
- leetcode 执行用时：28 ms —— 超过 100% 用户
原文
https://leetcode-cn.com/explore/learn/card/linked-list/193/singly-linked-list/741/
若有收获，就点个赞吧
0 人点赞
