python使用栈遇到的坑
两个链表生成相加链表
http://www.nowcoder.com/questionTerminal/c56f6c70fb3f4849bc56e33ff2a50b6b
本人习惯使用python，思路和一些C++写的代码思路一致，先使用stack1和stack2存储链表中的元素，然后从出栈累加构建新的链表，但是问题来了，C++写的代码可以通过但是使用python写的代码就超时无法通过，觉得题目测试存在问题，对python写的代码的时间复杂度应该相对放低些。
以下是运行超时的python代码：
class Solution: def addInList(self , head1 , head2 ): # write code here head = ListNode(0) stack1=[] stack2=[] while head1: stack1.append(head1) head1=head1.next while head2: stack2.append(head2) head2=head2.next if len(stack1)<len(stack2): stack1, stack2 = stack2, stack1 carry=0 while stack1&nbs***bsp;stack2&nbs***bsp;carry: if stack1: tmp = stack1.pop() carry+=tmp.val if stack2>0: carry+=stack2.pop().val tmp=ListNode(carry%10) carry=int(carry/10) tmp.next=head.next head.next=tmp return head.next重新审阅了这段代码发现生成累加和的链表的节点是不需要每次重新生成的，可以利用head1和head2中较长的那个链表，stack1保留较长的那个链表（注意数组中其实保留了链表的结构），tmp始终指向链表的头节点，最后判断carry是否为0，如果不为0，那么需要生成一个新的节点保留carry，然后将新节点的下个节点指向tmp。
class Solution: def addInList(self , head1 , head2 ): # write code here head = ListNode(0) stack1=[] stack2=[] while head1: stack1.append(head1) head1=head1.next while head2: stack2.append(head2) head2=head2.next if len(stack1)<len(stack2): stack1, stack2 = stack2, stack1 carry=0 tmp=None while stack1&nbs***bsp;stack2: if stack1: tmp = stack1.pop() carry+=tmp.val if stack2: carry+=stack2.pop().val tmp.val=carry%10 carry=int(carry/10) if carry: head=ListNode(carry) head.next=tmp return head else: return tmp
Momenta公司福利 417人发布
