python链表_递归求和_递归求最大小值

创建一个单链表：

class LinkNode:             #设置属性def __init__(self,data = None):self.data = dataself.next = None
class LinkList:             #设置头结点def __init__(self):self.head = LinkNode()self.head.next = Nonedef CreateListR(self,a):            #尾插法t = self.headfor i in range(len(a)):s = LinkNode(a[i])          #建立节点t.next = st = st.next = None                   #让尾结点变为空值
a = LinkList()
a.CreateListR([3,2,6,7,1])          #创建另一个单链表
b = LinkList()                  #
b.CreateListR([3,2,1])          #创建一个单链表

创建一个双链表：

class DlinkNode:def __init__(self,data = None):self.data = dataself.next = Noneself.prior = None
class Dlinklist:def __init__(self):self.dhead = DlinkNode()self.dhead.next = Noneself.dhead.prior = Nonedef CreatelistR(self,a):              #尾插法t = self.dheadfor i in range(len(a)):s = DlinkNode(a[i])t.next = ss.prior = tt = st.next = Nonedef getsize(self):                  #返回链表长度p = self.dheadcnt = 0while p.next != None:cnt+=1p = p.nextreturn cntdef geti(self,i):                   #返回序号为i的元素p = self.dheadj = -1while j<i and p.next!=None:j+=1p = p.nextreturn p
a = Dlinklist()
a.CreatelistR([1,2,3,4,5,6,9])

两个单链表递归求和：

def Sum(m):               #两个单链表求和if m==None:      #如果两个单链表尾节点的下一节点为空就返回0return 0else:return m.data+Sum(m.next)
p = Sum(a.head.next)
m = Sum(b.head.next)
print(p+m)

双链表用递归从中间求和：

def Sum(p,x):                     #双链表用递归从中间求和if p==None or x ==None:return 0else:return p.data+Sum(p.next,x.prior)+x.data    #p指针向后移动，x指针向前移动
size = a.getsize()              #获取整体长度if size%2==0:minddle = size//2               #找到中间序号it = a.geti(minddle)            #找到中间节点o = Sum(it,it.prior)            #注意传后面的it是要向前移一个print(o)
if size%2==1:minddle = size//2it = a.geti(minddle)o = Sum(it.next,it.prior)+it.dataprint(o)

用递归求链表的最小值：

def Min(p):                 #用递归求链表的最小值if p.next==None:        #只有一个就直接返回return p.datamin = Min(p.next)       #设为初始最小值if min<p.data:return min          #p向下移动else:return p.data       #返回最小值
a = Min(a.head.next)
print(a)