今天看到 待字闺中 的一道算法题:
两个单链表,每一个节点里面一个0-9的数字,输入就相当于两个大数了。然后返回这两个数字的和(一个新的list)。这两个输入的list长度相等。
要求: 1 不用递归 2 要求算法的时间和空间复杂度尽量低
分析:
0-9之间的数相加,最大的进位是1,如果只要求遍历两个链表各1次,需要两个指针辅助,一个指针指向第一个不是连续9的节点,第二个指针指向当前计算和的节点。为什么要这样设置指针?我们分情况来看:
Case1:
list1: 1 2 3 4 5
list2: 5 4 3 2 1
sum: 6 6 6 6 6
p,q
这种情况是最简单的,不产生进位,而且最高位也没有进位
case2:
list1: 2 4 6 7 8
list2: 3 5 3 2 7
sum: 5 9 9 9
p q
这是最复杂的情况:连续的9,这时候一旦当前求和的节点(q)产生了进位,之前所有的9都需要被置为0,而连续9之前的位(p)需要+1,这就是为什么要设置p在第一个不是连续9的节点,如果碰到了q有进位,就把p的节点+1, 然后p和q之间的所有节点置为0;
case3:
list1: 2 4 2 7 8
list2: 3 5 3 2 7
sum: 5 9 5
p q
这是居中的情况:没有连续的9,处理是当前的指针(q)得到的节点和为9时,p指针不动,如果q=q->next;之后,求得的节点指针小于9,即不可能产生进位,则把p指针指向当前的节点。
所有情况分析完毕,当然完事开头难,因为很可能第一位个高位就产生了进位,亦或者从最高位开始出现连续的9,所以我的处理办法是,只要第一位求和大于等于9,就建立两个节点,第一个节点存储sum/10;第二个节点存储sum%10;如果产生了进位也可以
ListNode* SumTwoList(const ListNode* list_1, const ListNode* list_2){ ListNode* head = new ListNode(0); ListNode* p; //p point to the first non-continuous-9 number, q point to the current node ListNode* q; p = q = head; list_1 = list_1->next; list_2 = list_2->next; int sum = list_1->data + list_2->data; //the first node should be traded specially, maybe there would be carry if(sum <9){ ListNode *node = new ListNode(sum); head->next = node; p = q = node; }else{ ListNode* node_1 = new ListNode(sum/10); ListNode* node_2 = new ListNode(sum%10); head->next = node_1; node_1->next = node_2; p = q = node_2; if(sum == 9) p = node_1; //if the sum equal with 9, p will not point to the node } while(list_1->next!= NULL && list_2->next!= NULL){ list_1 = list_1->next; list_2 = list_2->next; sum = list_1->data + list_2->data; ListNode* node = new ListNode(0); q->next = node; q = node; if(sum<=9){ //the current node is less than 9, there would never be a carry, so the p will follow the q node->data = sum; if(sum<9) p = q; }else{ node->data = sum%10; p->data += 1; p++; while(p!=q){ //all the node between q and p will be set to 0, because of the carry; p->data = 0; p++; } } } return head; }