编程算法面试常考题答案汇总
Design Linked List
Leetcode707 - Design Linked List
Design your implementation of the linked list. You can choose to use a singly or doubly linked list.
A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.
If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.
Solution
# 本代码来自 Techie科技求职，由 Techie Learning,Inc 原创
# - Techielearning.com 是来自硅谷的科技职业发展平台。
# - 本代码所属课程：<< Techie编程算法集训营 >>
# - 12周56+课时精品内容，精讲软件工程师编程算法面试核心知识体系。
# - 120道面试真题详解，27类常考题型剖析，1对1面试辅导与专业答疑。
# - 官方网站：https://www.techielearning.com/
# - 版权所有，禁止转发和分享
class ListNode(object):
def __init__(self, data, next = None):
self.data = data
self.next = next
class MyLinkedList:
def __init__(self):
self._head = None
self._tail = None
self._size = 0
def _get(self, head, index):
for _ in range(index):
head = head.next
return head
def _create_with_one_node(self, val):
self._head = self._tail = ListNode(val)
self._size = 1
def get(self, index: int) -> int:
if 0 <= index < self._size:
return self._get(self._head, index).data
else:
return -1
def addAtHead(self, val: int) -> None:
if self._size == 0:
self._create_with_one_node(val)
else:
self._head = ListNode(val, self._head)
self._size += 1
def addAtTail(self, val: int) -> None:
if self._size == 0:
self._create_with_one_node(val)
else:
self._tail.next = ListNode(val)
self._tail = self._tail.next
self._size += 1
def addAtIndex(self, index: int, val: int) -> None:
if index < 0 or index > self._size:
return
if index == self._size:
self.addAtTail(val)
elif index == 0:
self.addAtHead(val)
else:
pred = self._get(self._head, index - 1)
pred.next = ListNode(val, pred.next)
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
self._size -= 1
if self._size == 0:
self._tail = None
else:
pred = self._get(self._head, index - 1)
pred.next = pred.next.next
if index == self._size - 1:
self._tail = pred
self._size -= 1
def __str__(self):
strs = []
node = self._head
while node is not None:
strs.append(str(node.data))
node = node.next
return ' -> '.join(strs)
def __len__(self):
return self._size
如果大家对题目代码有任何问题，欢迎扫描下方的二维码或者搜索 TonyCoding20 添加Techie教师团队微信。期待与同学们继续交流！
