JZX轻语：简
LeetCode 707 - 设计链表
发表于2024年04月17日
链表数据结构设计题，比较传统的做法是只使用一个变量head来指向头节点。也可以再多一个变量tail来指向尾节点以加快addAtTail的速度，但每次新增/删除的时候都需要额外处理下tail。
仅使用head的版本：
from typing import NamedTuple, Optional
class LinkNode:
def __init__(self, val: int, next: Optional['LinkNode'] = None):
self.val = val
self.next = next
class MyLinkedList:
def __init__(self):
self._head = None # type: Optional[LinkNode]
def get(self, index: int) -> int:
curr_node = self._head
while curr_node is not None:
if index == 0:
return curr_node.val
index -= 1
curr_node = curr_node.next
# 遍历完所有的节点 index 都未消耗完毕
return -1
def addAtHead(self, val: int) -> None:
self._head = LinkNode(val, self._head)
def addAtTail(self, val: int) -> None:
dummy_head = LinkNode(-1, self._head)
prev_node = dummy_head
while prev_node.next is not None:
prev_node = prev_node.next
if prev_node is None:
return
new_node = LinkNode(val, prev_node.next)
prev_node.next = new_node
# 更新head
# 如果一开始为空链表, dummy_head的next为None
# 加上这一句可以覆盖所有的情况
self._head = dummy_head.next
def addAtIndex(self, index: int, val: int) -> None:
dummy_head = LinkNode(-1, self._head)
prev_node = dummy_head
while index:
prev_node = prev_node.next
if prev_node is None:
return
index -= 1
new_node = LinkNode(val, prev_node.next)
prev_node.next = new_node
# 更新head
# 如果一开始为空链表, dummy_head的next为None
# 加上这一句可以覆盖所有的情况
self._head = dummy_head.next
def deleteAtIndex(self, index: int) -> None:
dummy_head = LinkNode(-1, self._head)
prev_node = dummy_head
while index:
prev_node = prev_node.next
if prev_node is None:
return
index -= 1
if prev_node.next is None:
return
prev_node.next = prev_node.next.next
# 更新head
self._head = dummy_head.next使用head和tail的版本：
from typing import NamedTuple, Optional
class LinkNode:
def __init__(self, val: int, next: Optional['LinkNode'] = None):
self.val = val
self.next = next
class MyLinkedList:
def __init__(self):
self._head = None # type: Optional[LinkNode]
self._tail = None # type: Optional[LinkNode]
def get(self, index: int) -> int:
curr_node = self._head
while curr_node is not None:
if index == 0:
return curr_node.val
index -= 1
curr_node = curr_node.next
# 遍历完所有的节点 index 都未消耗完毕
return -1
def addAtHead(self, val: int) -> None:
self._head = LinkNode(val, self._head)
# 如果一开始为空链表, tail也需要更新
if self._tail is None:
self._tail = self._head
def addAtTail(self, val: int) -> None:
new_tail = LinkNode(val)
if self._tail is None:
# 如果一开始为空链表, head和tail都要更新
self._head = self._tail = new_tail
return
self._tail.next = new_tail
self._tail = new_tail
def addAtIndex(self, index: int, val: int) -> None:
dummy_head = LinkNode(-1, self._head)
prev_node = dummy_head
while index:
prev_node = prev_node.next
if prev_node is None:
return
index -= 1
new_node = LinkNode(val, prev_node.next)
prev_node.next = new_node
# 更新head和tail
if prev_node is self._tail:
# 如果是在原tail后面追加
self._tail = new_node
# 如果一开始为空链表, dummy_head的next为None
# 加上这一句可以覆盖所有的情况
self._head = dummy_head.next
def deleteAtIndex(self, index: int) -> None:
dummy_head = LinkNode(-1, self._head)
prev_node = dummy_head
while index:
prev_node = prev_node.next
if prev_node is None:
return
index -= 1
if prev_node.next is None:
return
prev_node.next = prev_node.next.next
# 更新head和tail
if prev_node.next is None:
# 如果删除的是tail
self._tail = prev_node
self._head = dummy_head.next