# 實(shí)現(xiàn)頭部插入 尾部插入 根據(jù)索引插入 刪除節(jié)點(diǎn)并print 打印
# 定義一個(gè)節(jié)點(diǎn)
class Node:
? ? def __init__(self, data):
? ? ? ? self.data = data
? ? ? ? self.next = None


class SingleLinkList:

? ? def __init__(self):
? ? ? ? self.head = None
? ? ? ? self.tail = None

? ? def is_empty(self):
? ? ? ? """鏈表是否為空
? ? ? ? :return:
? ? ? ? """
? ? ? ? return self.head is None

? ? def length(self):
? ? ? ? """求當(dāng)前鏈表的長(zhǎng)度
? ? ? ? :return:
? ? ? ? """
? ? ? ? count = 0
? ? ? ? cur = self.head

? ? ? ? while cur is not None:
? ? ? ? ? ? count += 1
? ? ? ? ? ? cur = cur.next

? ? ? ? return count

? ? def insert_head_node(self, data):
? ? ? ? """鏈表頭部添加元素
? ? ? ? :param data: 要保存的數(shù)據(jù)
? ? ? ? :return:
? ? ? ? """
? ? ? ? node = Node(data)
? ? ? ? node.next = self.head
? ? ? ? self.head = node

? ? def append_node(self, data):
? ? ? ? """鏈表尾部添加元素,有多種實(shí)現(xiàn)方式
? ? ? ? :param data:
? ? ? ? :return:
? ? ? ? """
? ? ? ? # 第一種方式 ?時(shí)間復(fù)雜度為O(n)的處理方式
? ? ? ? node = Node(data)
? ? ? ? # 如果鏈表為空,需要特殊處理
? ? ? ? if self.is_empty():
? ? ? ? ? ? self.head = node
? ? ? ? else:
? ? ? ? ? ? cur = self.head
? ? ? ? ? ? while cur.next is not None:
? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? # 退出循環(huán)時(shí), cur指向尾節(jié)點(diǎn)
? ? ? ? ? ? cur.next = node

? ? ? ? # 第二種 引入一個(gè)tail指針 默認(rèn)當(dāng)前鏈表為一個(gè)空鏈表,不停的去append節(jié)點(diǎn)

? ? ? ? # node = Node(data)
? ? ? ? # if self.is_empty(): ?# 當(dāng)?shù)谝淮翁砑庸?jié)點(diǎn)到空鏈表中的時(shí)候，頭指針和尾指針同時(shí)指向新節(jié)點(diǎn)
? ? ? ? # ? ? self.head = node
? ? ? ? # ? ? self.tail = node

? ? ? ? # else:
? ? ? ? # 當(dāng)再次添加節(jié)點(diǎn)到鏈表中的時(shí)候, 頭指針始終指向頭節(jié)點(diǎn)，尾指針始終執(zhí)行未節(jié)點(diǎn)，如果一直向未節(jié)點(diǎn)追加節(jié)點(diǎn)，只需移動(dòng)tail指針即可
? ? ? ? # ? ? self.tail.next = node
? ? ? ? # ? ? self.tail = node

? ? def insert_node(self, pos, data):
? ? ? ? """指定位置添加元素
? ? ? ? :param pos:
? ? ? ? :param data:
? ? ? ? :return:
? ? ? ? """
? ? ? ? # 1, 在頭部添加
? ? ? ? if pos <= 0:
? ? ? ? ? ? self.insert_head_node(data)
? ? ? ? # 2, 在尾部添加
? ? ? ? elif self.length() >= pos:
? ? ? ? ? ? self.append_node(data)
? ? ? ? # 3, 指定位置添加
? ? ? ? else:
? ? ? ? ? ? count = 0
? ? ? ? ? ? while count < (pos - 2):
? ? ? ? ? ? ? ? count += 1
? ? ? ? ? ? ? ? self.head = self.head.next

? ? ? ? ? ? # 這時(shí)候self.head 表示當(dāng)前插入前一個(gè)節(jié)點(diǎn)
? ? ? ? ? ? # self.head.next 表示當(dāng)前插入的后一個(gè)節(jié)點(diǎn)
? ? ? ? ? ? node = Node(data)
? ? ? ? ? ? self.head.next = node
? ? ? ? ? ? node.next = self.head.next

? ? def delete_node(self, data):
? ? ? ? """刪除節(jié)點(diǎn)
? ? ? ? :param data:
? ? ? ? :return:
? ? ? ? """
? ? ? ? cur = self.head ? ? # 記錄當(dāng)前節(jié)點(diǎn)的位置
? ? ? ? pre = None ? ? ? ? ?# 記錄當(dāng)前節(jié)點(diǎn)位置的前置節(jié)點(diǎn)
? ? ? ? while cur is not None:
? ? ? ? ? ? # 找到了要?jiǎng)h除的元素
? ? ? ? ? ? if cur.data == data:
? ? ? ? ? ? ? ? # 在頭部找到了要?jiǎng)h除的元素
? ? ? ? ? ? ? ? if cur == self.head:
? ? ? ? ? ? ? ? ? ? self.head = cur.next
? ? ? ? ? ? ? ? ? ? return True
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? pre.next = cur.next
? ? ? ? ? ? ? ? ? ? return True
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? # 不是要找的元素, 移動(dòng)光標(biāo)
? ? ? ? ? ? ? ? pre = cur
? ? ? ? ? ? ? ? cur = cur.next

? ? def search_node(self, data):
? ? ? ? """查找節(jié)點(diǎn)是否存在
? ? ? ? :return:
? ? ? ? """
? ? ? ? cur = self.head
? ? ? ? while cur is not None:
? ? ? ? ? ? if cur.data == data:
? ? ? ? ? ? ? ? return True
? ? ? ? ? ? cur = cur.next
? ? ? ? return False

? ? def reveres_node(self):
? ? ? ? """鏈表反轉(zhuǎn)
? ? ? ? :return:
? ? ? ? """
? ? ? ? if self.is_empty():
? ? ? ? ? ? return
? ? ? ? j = 0
? ? ? ? while j < self.length() - 1:
? ? ? ? ? ? cur = self.head
? ? ? ? ? ? for i in range(self.length() - 1):
? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? ? ? if cur.next is None:
? ? ? ? ? ? ? ? ? ? x = cur.data
? ? ? ? ? ? ? ? ? ? self.delete_node(cur.data)
? ? ? ? ? ? ? ? ? ? self.insert_node(j, x)
? ? ? ? ? ? j += 1
? ? ? ? return self.head