[算法]单链表之和

简介:

今天看到 待字闺中 的一道算法题:

两个单链表,每一个节点里面一个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;
}



目录
相关文章
|
6月前
|
存储 算法 索引
数据结构与算法:单链表
朋友们大家好,本节来到数据结构与算法的新内容:单链表 在上篇文章中,我们知道顺序表通常需要预分配一个固定大小的内存空间, 通常以二倍的大小进行增容,可能会造成空间的浪费,本篇文章我们介绍的链表可以解决这个问题
|
6月前
|
存储 JavaScript 算法
TypeScript算法专题 - blog1.基于TypeScript语言的单链表实现
TypeScript算法专题 - blog1.基于TypeScript语言的单链表实现
74 0
|
6月前
|
存储 JavaScript 算法
TypeScript算法专题 - blog4 - 单链表节点的两-两翻转(两两一组逆序)
TypeScript算法专题 - blog4 - 单链表节点的两-两翻转(两两一组逆序)
51 0
|
25天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
25 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
3月前
|
算法 索引
【初阶数据结构篇】单链表算法题进阶
深拷贝应该正好由 n 个全新节点组成,其中每个新节点的值都设为其对应的原节点的值。
23 0
|
5月前
|
算法 程序员 数据处理
【数据结构与算法】使用单链表实现队列:原理、步骤与应用
【数据结构与算法】使用单链表实现队列:原理、步骤与应用
|
5月前
|
算法 C语言
【数据结构与算法 经典例题】返回单链表的倒数第 k 个节点
【数据结构与算法 经典例题】返回单链表的倒数第 k 个节点
|
5月前
|
存储 算法 C语言
【数据结构与算法】深入理解 单链表
【数据结构与算法】深入理解 单链表
|
5月前
|
算法
数据结构和算法学习记录——线性表之单链表(下)-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁
数据结构和算法学习记录——线性表之单链表(下)-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁
62 0
|
5月前
|
存储 算法
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数(顺序表缺陷、单链表优点、链表打印)
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数(顺序表缺陷、单链表优点、链表打印)
37 0