"""節(jié)點(diǎn)類"""


class Node(object):
  def __init__(self, data):
    self.data = data
    self.nex = None

def __init__(self):
  """初始化鏈表"""
  self.head = None

def __len__(self):
  pre = self.head
  length = 0
  while pre:
    length += 1
    pre = pre.nex
  return length

"""追加節(jié)點(diǎn)"""

def append(self, data):
  """
  1.head 為none :head-->node
  2.tail.nex-->node
  :param data:
  :return:
  """
  node = Node(data)
  if self.head is None:
    self.head = node
  else:
    pre = self.head
    while pre.nex:
      pre = pre.nex
    pre.nex = node

def get(self, index):
  """
  :param index:
  :return:
  """
  index = index if index >= 0 else len(self) + index
  if len(self) < index or index < 0:
    return None
  pre = self.head
  while index:
    pre = pre.nex
    index -= 1
  return pre

"""設(shè)置節(jié)點(diǎn)"""

def set(self, index, data):
  node = self.get(index)
  if node:
    node.data = data
  return node

"""插入節(jié)點(diǎn)"""

def insert(self, index, data):
  """
  1.index 插入節(jié)點(diǎn)位置包括正負(fù)數(shù)
  2.找到index-1-->pre_node的節(jié)點(diǎn)
  3.pre_node.next-->node
   node.next-->pre_node.next.next
  4.head
  :param index:
  :param data:
  :return:
  """
  node = Node(data)
  if abs(index + 1) > len(self):
    return False
  index = index if index >= 0 else len(self) + index + 1
  if index == 0:
    node.nex = self.head
    self.head = node
  else:
    pre = self.get(index - 1)
    if pre:
      nex = pre.nex
      pre.nex = node
      node.nex = nex
    else:
      return False
  return node

"""刪除某個(gè)元素"""

def delete(self, index):
  f = index if index > 0 else abs(index + 1)
  if len(self) <= f:
    return False
  pre = self.head
  index = index if index >= 0 else len(self) + index
  prep = None
  while index:
    prep = pre
    pre = pre.nex
    index -= 1
  if not prep:
    self.head = pre.nex
  else:
    prep.nex = pre.nex
  return pre.data

"""反轉(zhuǎn)鏈表"""

def __reversed__(self):
  """
  1.pre-->next 轉(zhuǎn)變?yōu)?next-->pre
  2.pre 若是head 則把 pre.nex --> None
  3.tail-->self.head
  :return:
  """

  def reverse(pre_node, node):
    if pre_node is self.head:
      pre_node.nex = None
    if node:
      next_node = node.nex
      node.nex = pre_node
      return reverse(node, next_node)
    else:
      self.head = pre_node

  return reverse(self.head, self.head.nex)

"""清空鏈表"""

def clear(self):
  self.head = None