发表于 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

• LC 题目链接