# 實現頭部插入 尾部插入 根據索引插入 刪除節點并print 打印
# 定義一個節點
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):
? ? ? ? """求當前鏈表的長度
? ? ? ? :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: 要保存的數據
? ? ? ? :return:
? ? ? ? """
? ? ? ? node = Node(data)
? ? ? ? node.next = self.head
? ? ? ? self.head = node

? ? def append_node(self, data):
? ? ? ? """鏈表尾部添加元素,有多種實現方式
? ? ? ? :param data:
? ? ? ? :return:
? ? ? ? """
? ? ? ? # 第一種方式 ?時間復雜度為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
? ? ? ? ? ? # 退出循環時, cur指向尾節點
? ? ? ? ? ? cur.next = node

? ? ? ? # 第二種 引入一個tail指針 默認當前鏈表為一個空鏈表,不停的去append節點

? ? ? ? # node = Node(data)
? ? ? ? # if self.is_empty(): ?# 當第一次添加節點到空鏈表中的時候，頭指針和尾指針同時指向新節點
? ? ? ? # ? ? self.head = node
? ? ? ? # ? ? self.tail = node

? ? ? ? # else:
? ? ? ? # 當再次添加節點到鏈表中的時候, 頭指針始終指向頭節點，尾指針始終執行未節點，如果一直向未節點追加節點，只需移動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

? ? ? ? ? ? # 這時候self.head 表示當前插入前一個節點
? ? ? ? ? ? # self.head.next 表示當前插入的后一個節點
? ? ? ? ? ? node = Node(data)
? ? ? ? ? ? self.head.next = node
? ? ? ? ? ? node.next = self.head.next

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

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

? ? def reveres_node(self):
? ? ? ? """鏈表反轉
? ? ? ? :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