知之者不如好之者，好之者不如乐之者。——《雍也》
知道德者不如好道德者，好道德者不如乐道德者，是为形容人道德之深。
电脑修好了。
题目：给定两个链表，链表的每一个节点代表一位数，个位数在链表的前面，要求两个链表所代表的整数的和，并用一个链表表示出来。例如：head1->1->3->4->5 和 head2->2->1->6->2，所代表的数分别为：54311，26122，=>54311+26122=80433,用链表表示为Head->3->3->4->0->8。
今天的题目说简单，却有点复杂，说复杂却很好理解(废话)。往简单的说:分别求出两个链表代表的整数，相加，将结果存入链表输出即可。你肯定会想：这太简单了，操作起来没有任何难度。不管如何，我们先来看一下这“简单”到底简不简单。
求链表的和：因为每个节点保存的是一位数，每向后遍历一个节点，都要乘10^n，并累加到sum。但是n越来越大，sum也越来越大。最终会超过长整型的最大范围，那怎么办呢，后面我会详细讲，现在先来看看，怎么实现这“简单的方法”：这里我用的reduce函数，这个函数在python3里是被封装到了functools 里。可能有同学不太了解这个函数(我自己也不太熟，这里是一次小练习，混个脸熟)——这里有个直通车map/reduce可以让大家理解这个函数。这个函数用来求累加和非常容易。 也可以不用这个，可以用一个i来保存当前是第几位，然后边遍历，边求和，同样能求出来。
from functools import reduce
#用于求和
def fn(x,y):
return x*10+y
#求链表所代表的数
def sumlink(head):
Sum=0#保存和
cur=head.next
List=[]#用于保存链表的每一个节点
while cur is not None:
#将节点保存在第一位
List.insert(0,cur.data)
cur=cur.next
if head is not None or head.next is not None:
Sum=reduce(fn,List)
print("head's Sum :",Sum)
return Sum
这里现在我不太熟，以后我找时间学学。
下面的是将和存入链表的函数：将和从整型转换为字符串，让其可迭代。然后依次存入，然后逆序链表，这被我之前写复杂了，逆序用的是第一次写的就地逆序法，因为当时对递归法、插入法还不熟悉，所以代码不够精简。其实完全可以先把字符串逆序，然后放进去，但是字符串逆序又要一步操作，实在是太繁琐了，违背了python精简的初衷，当初也是没多想，就当时复习一下了。但是在面试时遇到这样的问题时，一定不要用这个方法。因为费时费力，还容易出错，光是前面的求链表对应的整数都是一个问题。不过这里还是给出代码：
def function(head1,head2):
Sum=sumlink(head1)+sumlink(head2)
print("sum is ",Sum)
Sum=str(Sum)
head=LNode(None)
cur=head
tmp=None
for i in Sum:
tmp=LNode(i)
cur.next=tmp
cur=cur.next
#开始逆序链表——就地逆序法
# 判断链表是否为空
if head is None or head.next is None:
return
# 处理链表头
cur = head.next
next = cur.next
cur.next = None
pre = cur
cur = next
# 转变当前节点指向
while cur.next != None:
next = cur.next
cur.next = pre
pre = cur
cur = next
# 处理最后一个节点与倒数第二个节点
cur.next = pre
# 添加头节点
head.next = cur
return head
主程序：
if __name__ == '__main__':
head1=creatLink(10)
head2=creatLink(10)
print("head1:")
cur = head1.next
while cur != None:
print(cur.data)
cur = cur.next
print("head2:")
cur = head2.next
while cur != None:
print(cur.data)
cur = cur.next
head = function(head1,head2)
print("\nAfteplus:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
输出结果：
输出结果
虽然过程曲折，但是我们还是完成了这个题目的要求。但是这种方法的缺点非常明显，一旦链表保存的整数超过了长整型的最大数值，程序就会报错。明天我会介绍链表直接相加的方法，这种方法就像是一种加法器，是一位一位加的，更符合我们平时的计算方法。而且理论上，只要你电脑内存够，就可以一直算下去。这比上面的方法好多了。
全部的代码如下：
import random
from functools import reduce
class LNode:
"""docstring for LNode"""
def __init__(self, arg):
self.data = arg
self.next = None
"""
题目描述：
将Head->1->1->3->3->5->7->7->8
与head->1->2->5->7->8相加
得Head->2->3->8->0->4->8->7->8
个位在前
方法：整数相加，先求h1的和，再求h2的和，然后相加，最后根据和新建链表
"""
#构造链表
def creatLink(x):
i = 1
head = LNode(None)
tmp = None
cur = head
while i <= x:
n = random.randint(1, 9)
tmp = LNode(n)
cur.next = tmp
cur = tmp
i += 1
return head
#用于求和
def fn(x,y):
return x*10+y
#求链表所代表的数
def sumlink(head):
Sum=0#保存和
cur=head.next
List=[]#用于保存链表的每一个节点
while cur is not None:
#将节点保存在第一位
List.insert(0,cur.data)
cur=cur.next
if head is not None or head.next is not None:
Sum=reduce(fn,List)
print("head's Sum :",Sum)
return Sum
def function(head1,head2):
Sum=sumlink(head1)+sumlink(head2)
print("sum is ",Sum)
Sum=str(Sum)
head=LNode(None)
cur=head
tmp=None
for i in Sum:
tmp=LNode(i)
cur.next=tmp
cur=cur.next
# 判断链表是否为空
if head is None or head.next is None:
return
# 处理链表头
cur = head.next
next = cur.next
cur.next = None
pre = cur
cur = next
# 转变当前节点指向
while cur.next != None:
next = cur.next
cur.next = pre
pre = cur
cur = next
# 处理最后一个节点与倒数第二个节点
cur.next = pre
# 添加头节点
head.next = cur
return head
if __name__ == '__main__':
head1=creatLink(10)
head2=creatLink(10)
print("head1:")
cur = head1.next
while cur != None:
print(cur.data)
cur = cur.next
print("head2:")
cur = head2.next
while cur != None:
print(cur.data)
cur = cur.next
head = function(head1,head2)
print("\nAfteplus:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
今天的就先讲到这里了，今天的算法其实也没多大用，所以注释就没写这么详细，但是电脑刚修好，很多东西还在弄。昨天提到的流程图还要一段时间，最近学校课程安排也是很紧，明天晚上要上课，可能明天的算法会晚一点。等周五我才空下来，我会好好整理下。争取在周末给大家分享一个小爬虫案例。爬哪个网站还没想好，就先这样子。
还是那句话，我只是需要被需要——再我的github有所有的代码，当然可能会有所出入，但相差不多，欢迎大家学习！
这是我微信公众号：Dkider 方便大家联系我。
DKider
君子之于天下也，无适也，无莫也，义之与比。——《论语》
网友评论