剑指offer--algorithm7

题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.png
image.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()