两个链表进行求和操作，我们可以将每个链表的每一个节点存储的整数看作是整数的某一个数位的数字。两个链表求和，即遍历两个链表的节点，将每一个数位的整数进行加法操作，其结果作为新链表的一个节点返回。
两个链表进行求和操作，我们可以将每个链表的每一个节点存储的整数看作是整数的某一个数位的数字。两个链表求和，即遍历两个链表的节点，将每一个数位的整数进行加法操作，其结果作为新链表的一个节点返回。
例子：两个链表分别为 1->0->3 和 2->1->4,则链表求和后返回的新链表为 3->1->7
链表逐位遍历应该从链表末尾往链表头部进行，从而同实际的整数加法从低位到高位的计算方式一致，并且需要考虑到进位问题。
按照题目要求，用栈这个数据结构保存遍历过程中两个链表的节点，在出栈时进行求和计算。
算法实现如下：
class InfoQTest {public:
ListNode* listAddOperation(ListNode* head1, ListNode* head2) {
if(head1 === null) { return head2; } if(head2 === null) { return head1; } stack<ListNode*>s1; stack<ListNode*>s2; while(head1 != null){ s1.push(head1); head1=head1->next; } while(head2 != null){ s2.push(head2); head2=head2->next; } int flag = 0; while(!s1.empty()||!s2.empty()){ int sum = flag; if(!s1.empty()){ sum += s1.top()->val; head1 = s1.top(); s1.pop(); } if(!s2.empty()){ sum += s2.top()->val; if(s1.size()<s2.size()){ head1=s2.top(); s2.pop(); } } flag = sum/10; head1->val = sum % 10; } if( flag > 0) { ListNode* node = new ListNode(1); node->next = head1; return node; } return head1; }};
复制代码
评论