实现了python单向链表及一些算法题
from functools import wraps
class Node(object):
def __init__(self,next_node=None,value=''):
self.value = value
self.next_node = next_node
class Chain(object):
def __init__(self,head = None):
self.head = head
# 获取长度
def get_length(self):
length = 1
assert (self.head)
cur_node = self.head
while cur_node.next_node:
length+=1
cur_node = cur_node.next_node
return length
# 构建链表
def create(self,list):
assert (len(list)>0)
self.head = Node(None,list[0])
if len(list) == 1:
return
else:
cur = self.head
for i in list[1:]:
cur.next_node = Node(None,i)
cur = cur.next_node
# 装饰器
def show(name):
def decorator(func):
@wraps(func)
def wrapper(self,*args, **kwargs):
self._show()
result = func(self,*args, **kwargs)
self._show(name)
print('\n')
return result
return wrapper
return decorator
# 遍历链表
def _show(self,name='原链表'):
assert (self.head)
dummy_node = Node(self.head)
cur_node = dummy_node
print(name+':', end="")
while cur_node.next_node:
cur_node = cur_node.next_node
print(str(cur_node.value) + '->', end="")
print('None')
del dummy_node
# 翻转链表
@show('翻转链表')
def reverse(self):
cur_node = self.head
pre_node = None
while cur_node:
temp_node = cur_node.next_node
cur_node.next_node = pre_node
pre_node = cur_node
cur_node = temp_node
self.head = pre_node
# 删除链表中第一个value为value的节点
@show('删除第一个value')
def remove_one(self,value):
cur_node = self.head
if cur_node.value==value:
self.head = cur_node.next_node
del cur_node
else:
while cur_node.next_node:
if cur_node.next_node.value == value:
del_node = cur_node.next_node
cur_node.next_node = del_node.next_node
del del_node
break
else:
cur_node = cur_node.next_node
# 删除链表中所有value为value的节点
@show('删除所有value')
def remove_all(self,value):
cur_node = self.head
while cur_node.value == value:
cur_node = cur_node.next_node
self.head = cur_node
if cur_node.value==value and cur_node.next_node is None:
self.head = cur_node.next_node
del cur_node
else:
while cur_node.next_node:
if cur_node.next_node.value == value:
del_node = cur_node.next_node
cur_node.next_node = del_node.next_node
del del_node
else:
cur_node = cur_node.next_node
# 根据给定的标记位置翻转链表
def reverse_index(self,start,end):
length = self.get_length()
if start<=0 or end<=0 or end>length or start>length:
raise Exception('错误的位置标记')
if start == end:
return
n=0
dumpy_node = Node(self.head)
unswaped_pre_node = dumpy_node
self.head = dumpy_node
cur_node = self.head
while n < start and cur_node.next_node:
n+=1
unswaped_pre_node = cur_node #标记未被交换位置的最前节点
cur_node = cur_node.next_node
swaped_pre_node = cur_node #标记被交换位置的最前节点
post_node = cur_node.next_node
while n < end:
n+=1
unswaped_post_node = post_node.next_node #标记未被交换位置的最后节点
swaped_post_node = post_node #标记被交换位置的最后节点
post_node.next_node = cur_node
cur_node = post_node
post_node = unswaped_post_node #不断更新最前的节点
unswaped_pre_node.next_node = swaped_post_node
swaped_pre_node.next_node = unswaped_post_node
self.head = dumpy_node.next_node
del dumpy_node
# 去除有序链表的相同value节点
@show('去除有序链表相同项')
def set_sorted_chain(self):
cur_node = self.head
while cur_node and cur_node.next_node:
if cur_node.value == cur_node.next_node.value:
del_node = cur_node.next_node
cur_node.next_node = del_node.next_node
del del_node
else: #没有删除节点才向前移动节点
cur_node = cur_node.next_node
# 根据给定的x值,将链表分成2部分.左边小于x,右边大于等于x
@show('链表分成两部分')
def two_partition(self,x):
dummy_node = Node(self.head)
cur_node = dummy_node.next_node #创建一个虚假节点成为头节点
# 先找到value为x的节点
while cur_node:
if cur_node.value == x:
x_node = cur_node
cur_node = cur_node.next_node
else:
cur_node = cur_node.next_node
assert (x_node) # 如果不存在则表示x标记错误
cur_node = dummy_node.next_node
pre_x_node = None # 接在x_node前的第一个节点
post_x_node,flag = None,True # 接在x_node后的第一个节点,通过flag来绑定
pre_min_node = dummy_node # 保存小于x_node节点的前一个节点
pre_max_node = None # 保存大于x_node节点的前一个节点
while cur_node:
if cur_node.value < x:
pre_min_node.next_node = cur_node
pre_min_node = cur_node
pre_x_node = cur_node
elif cur_node.value > x:
if flag:
post_x_node = cur_node
flag = False
if pre_max_node is None:
pre_max_node = cur_node
else:
pre_max_node.next_node = cur_node
pre_max_node = cur_node
elif cur_node == x_node:
pass
cur_node = cur_node.next_node
pre_max_node.next_node = None
x_node.next_node = post_x_node
pre_x_node.next_node = x_node
self.head = dummy_node.next_node
del dummy_node
# merge两个有序链表
@show('merge两个有序链表')
def merge(self,another_chain):
assert (another_chain.head)
cur_node = self.head
cur_node1 = another_chain.head
head_node = cur_node if cur_node.value<=cur_node1.value else cur_node1 #选出起始节点
dummy_node = Node(head_node) #选出一个虚假的头节点
tmp_node = dummy_node
while cur_node or cur_node1:
if not cur_node:
tmp_node.next_node = cur_node1
tmp_node = cur_node1
cur_node1 = cur_node1.next_node
elif not cur_node1:
tmp_node.next_node = cur_node
tmp_node = cur_node
cur_node = cur_node.next_node
elif cur_node.value <= cur_node1.value:
tmp_node.next_node = cur_node
tmp_node = cur_node
cur_node = cur_node.next_node
else: # cur_node1.value < cur_node.value
tmp_node.next_node = cur_node1
tmp_node = cur_node1
cur_node1 = cur_node1.next_node
self.head = dummy_node.next_node
del dummy_node
# 判定链表是否为回文结构
@show('判定是否为回文结构')
def judge_palindrome(self):
slow_node = self.head # 每次走一步
slow_index = 1
fast_node = self.head #每次走两步
fast_index = 1
if not slow_node.next_node: #只有一个头节点
print('是回文结构')
return True
while slow_node.next_node and fast_node.next_node:
if not fast_node.next_node.next_node: # 偶数个节点
fast_node = fast_node.next_node
fast_index+=1
else: # 奇数个节点
slow_node = slow_node.next_node
slow_index+=1
fast_node = fast_node.next_node.next_node
fast_index+=2
self.reverse_index(slow_index+1, fast_index)
flag_node = slow_node.next_node if fast_index % slow_index == 0 else slow_node # slow_cur_node不能到达的节点
slow_cur_node = self.head
fast_cur_node = slow_node.next_node
while slow_cur_node.next_node != flag_node:
if slow_cur_node.value == fast_cur_node.value:
slow_cur_node = slow_cur_node.next_node
fast_cur_node = fast_cur_node.next_node
else:
print('不是回文结构')
return
print('是回文结构')
# L(0) -> L(1) -> L(2) .... -> L(n-1) -> L(n)
# L(0) -> L(n) -> L(1) .... -> L(n-1) -> L(2)
# 逆序穿插链表
@show('逆序穿插链表')
def reorder_list(self):
if not self.head.next_node:
return
slow_node = self.head # 每次走一步
slow_index = 1
fast_node = self.head # 每次走两步
fast_index = 1
while slow_node.next_node and fast_node.next_node:
if not fast_node.next_node.next_node: # 偶数个节点
fast_node = fast_node.next_node
fast_index+=1
else: # 奇数个节点
slow_node = slow_node.next_node
slow_index+=1
fast_node = fast_node.next_node.next_node
fast_index+=2
pre_node = slow_node.next_node
slow_node.next_node = None
cur_node = pre_node.next_node
pre_node.next_node = None
while cur_node:
later_node = cur_node.next_node
cur_node.next_node = pre_node
pre_node = cur_node
cur_node = later_node
node1 = self.head
node2 = pre_node
dummy_node = Node(node1) #选出一个虚假的头节点
tmp_node = dummy_node
n = 1
while node1 or node2:
if n%2==1 and node1:
tmp_node.next_node = node1
tmp_node = node1
node1 = node1.next_node if node1.next_node else None
n =2
elif n%2==0 and node2:
tmp_node.next_node = node2
tmp_node = node2
node2 = node2.next_node if node2.next_node else None
n =1
elif node1:
tmp_node.next_node = node1
node1 = node1.next_node if node1.next_node else None
elif node2:
tmp_node.next_node = node2
node2 = node2.next_node if node2.next_node else None
del dummy_node
#给定一个链表,让这个链表向右旋转K位,其中k为非负数
#如: 1>2>3>4>5>NULL k = 2
#第一次旋转: 5>1>2>3>4>NULL
#第二次旋转: 4>5>1>2>3>NULL
@show('旋转链表')
def rotate_list(self,k):
assert (k>=0)
chain_length = self.get_length()
real_k = k % chain_length
if real_k == 0: return
slow_node = self.head
fast_node = self.head
while real_k>0 and fast_node.next_node:
fast_node = fast_node.next_node
real_k-=1
while fast_node.next_node:
fast_node = fast_node.next_node
slow_node = slow_node.next_node
fast_node.next_node = self.head
self.head = slow_node.next_node
slow_node.next_node = None
# 给定一个链表,让这个链表向右旋转K位,其中k为非负数
# 如: 1>2>3>4>5>NULL k = 2
# 第一次旋转: 5>1>2>3>4>NULL
# 第二次旋转: 4>5>1>2>3>NULL
#如: 1>2>3>4>5>NULL,k=2
#返回: 1>2>3>5>NULL
@show('倒数k数删除链表')
def romove_node_from_end(self, k):
assert (k>0)
slow_node = Node(self.head)
del_node = self.head
fast_node = self.head
cur_index = 1
while cur_index<k and fast_node.next_node:
fast_node = fast_node.next_node
cur_index+=1
if cur_index!=k:
print('k值超过了链表长度')
return
if not fast_node.next_node:
self.head = self.head.next_node
del del_node
return
while fast_node.next_node:
slow_node = slow_node.next_node
del_node = del_node.next_node
fast_node = fast_node.next_node
slow_node.next_node = del_node.next_node
del del_node
#给定一个链表,每k个节点为一组,反转每一组的k个节点.k为正整数且小于等于链表长度.如果链表长度不是k整数倍,剩余部分不需要反转.
#如 1>2>3>4>5>NULL
#若k=2,则结果为: 2>1>4>3>5>NULL
#若k=3,则结果为: 3>2>1>4>5>NULL
@show('根据K值反转链表')
def reverse_nodes_in_kgroup(self,k):
assert (k>=1)
cur_node = self.head
n = 1 #当前轮次进行到的节点
cur_n = 1 #当前行进到了节点
while cur_node.next_node:
while n<k and cur_node:
cur_node = cur_node.next_node
n+=1
cur_n+=1
if n==k:
cur_node = cur_node.next_node
self.reverse_index(cur_n - 2, cur_n)
if not cur_node:
return
n = 1
cur_n += 1
else: #意味着到底部了
return
chain = Chain()
# 删除第一个指定value
x=[1,4,5,4,5,6,7,1,1,3]
chain.create(x)
chain.remove_one(1)
# 删除所有指定value
x=[1,1,1,4,5,4,5,6,7,1,1,3]
chain.create(x)
chain.remove_all(1)
# 翻转链表
x=[1,1,1,4,5,4,5,6,7,1,1,3]
chain.create(x)
chain.reverse()
# 去除有序链表的相同value节点
x=[1,1,1,3,3,4,4]
chain.create(x)
chain.set_sorted_chain()
# 根据给定的x值,将链表分成2部分.左边小于x,右边大于等于x
x=[1,1,1,4,5,4,5,6,7,1,1,3]
chain.create(x)
chain.two_partition(3)
# 将两个有序链表merge
x=[1,3,5,7]
y=[0,2,4,6,8]
chain.create(x)
chain1 = Chain()
chain1.create(y)
chain.merge(chain1)
# 判定是否为回文结构
x=[1,2,3,4,5,4,3,2,1]
chain.create(x)
chain.judge_palindrome()
# 逆序穿插链表
x=[1,2,3,4,5,6,7,8,9]
chain.create(x)
chain.reorder_list()
# 旋转链表
x=[1,2,3,4,5,6,7,8,9]
chain.create(x)
chain.rotate_list(3)
# 倒数k数删除链表
x=[1,2,3,4,5,6,7,8,9]
chain.create(x)
chain.romove_node_from_end(9)
# 根据K值反转链表
x=[1,2,3,4,5,6,7,8,9]
chain.create(x)
chain.reverse_nodes_in_kgroup(3)
output：
原链表:1->4->5->4->5->6->7->1->1->3->None
删除第一个value:4->5->4->5->6->7->1->1->3->None
原链表:1->1->1->4->5->4->5->6->7->1->1->3->None
删除所有value:4->5->4->5->6->7->3->None
原链表:1->1->1->4->5->4->5->6->7->1->1->3->None
翻转链表:3->1->1->7->6->5->4->5->4->1->1->1->None
原链表:1->1->1->3->3->4->4->None
去除有序链表相同项:1->3->4->None
原链表:1->1->1->4->5->4->5->6->7->1->1->3->None
链表分成两部分:1->1->1->1->1->3->4->5->4->5->6->7->None
原链表:1->3->5->7->None
merge两个有序链表:0->1->2->3->4->5->6->7->8->None
原链表:1->2->3->4->5->4->3->2->1->None
是回文结构
判定是否为回文结构:1->2->3->4->5->1->2->3->4->None
原链表:1->2->3->4->5->6->7->8->9->None
逆序穿插链表:1->9->2->8->3->7->4->6->5->None
原链表:1->2->3->4->5->6->7->8->9->None
旋转链表:7->8->9->1->2->3->4->5->6->None
原链表:1->2->3->4->5->6->7->8->9->None
倒数k数删除链表:2->3->4->5->6->7->8->9->None
原链表:1->2->3->4->5->6->7->8->9->None
根据K值反转链表:3->2->1->6->5->4->9->8->7->None
网友评论