剑指offer--algorithm7
2018-05-10 本文已影响0人
strive鱼
题14--翻转链表
输入一个链表。翻转链表后,输出链表的所有元素
一般提到链表的翻转,就需要指针的一个转换,当有多个节点的时候,就容易出错,因此书中提供了一个方法,需要设立三个指针
image.png
image.png
image.png
class node(object):
def __init__(self,value=None,next=None):
self.value=value
self.next=None
class solution(object):
def reverselist(self,phead):#参数为头结点
if phead==None or phead.next==None:
return phead
preverse_head=None#后只针对的位置
pnode=phead#第二个指针的位置设定在当前节点
p_prev=None#第三个节点的位置设置在当前节点的前面
while pnode!=None:
pnext=pnode.next#将当前节点的下一个节点进行实例化
if pnext==None:#表明已经到了尾部
preverse_head=pnode
pnode.next=p_prev
p_prev=pnode
pnode=pnext#通过这三部调换指针
return preverse_head#循环结束后,输出反转后的链表
def main():
n1=node(1)
n2=node(2)
n3=node(3)
n4=node(4)
n5=node(5)
n1.next=n2
n2.next=n3
n3.next=n4
n4.next=n5
s=solution()
print (s.reverselist(n1))
if __name__=='__main__':
main()
题15--合并两个链表
分别给出了两个单调递增的链表,合并链表后,仍然是单调递增的
关于本题的思路和鲁棒性的解决,书中描述到位,如下
image.png image.pngimage.png
image.png
下面为代码和注释部分
"""
下面代码输出为1,2,3,4,5,6比较直观
"""
class node(object):
def __init__(self,value):
self.value=value
self.next=None
class solution(object):
def merge(self,phead1,phead2):#参数为两个表头
if phead1==None and phead2!=None:
return phead2
elif phead1!=None and phead2==None:
return phead1
elif phead1==None and phead2==None:
return None
else:
pmerge_head=None#初始化合并后链表的表头
if phead1.value<phead2.value:
pmerge_head=phead1#按照书中的思路,将其单独拉出来作为合并后的新的链表的表头
pmerge_head.next=self.merge(phead1.next,phead2)
else:
pmerge_head=phead2#按照书中的思路,将其单独拉出来作为合并后的新的链表的表头
pmerge_head.next=self.merge(phead1,phead2.next)
return pmerge_head
def logging (self,structure_node):#用于打印观察链表的结构
while structure_node!=None:
print ('value',structure_node.value)
structure_node=structure_node.next
def main():
n1=node(1)
n2=node(3)
n3=node(5)
n1.next=n2
n2.next=n3
n4=node(2)
n5=node(4)
n6=node(6)
n4.next=n5
n5.next=n6
s=solution()
s.logging(s.merge(n1,n4))
if __name__=='__main__':
main()