70
技術社區[雲棲]
[算法]單鏈表之和
今天看到 待字閨中 的一道算法題：
兩個單鏈表，每一個節點裏麵一個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;
}
最後更新：2017-04-03 16:48:31