leetcode【第一周】:单链表表示的两个数字相加

75 阅读 0 评论 50 点赞

我是靠谱客的博主微笑纸飞机，最近开发中收集的这篇文章主要介绍leetcode【第一周】:单链表表示的两个数字相加，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题描述：

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

解答思路：

如题所描述，两个数值使用单链表来存储，链表每一个节点存储一个数字，从链表头开始，由低位到高位，一开始想到把两个链表都遍历一遍，算出所表示的数值，然后相加得到答案后再构建要返回的链表，显然这不可能是出题者的意图。那么就从单链表的属性方面以及对单链表的操作来考虑。因而我们能想到，对应位的数值进行相加然后再判断是否向高位进位即可,而每次向高位的进位最大值是1，最小值是0，因为单个数字最大是9，那么算上上一位的进位，当前向高位的进位值最大是1+9+9=19，小于20。为了实现我们的想法，我们需要知道一个问题，当两条链表不一样长时，哪条链表更长些，以便当我们做完两条链表相对应的部分后判断是否需要对较长链表的剩余部分继续进行进位计算。显然，做完第一遍相加的迭代后，指针所指的节点不为空的链表要长些。另外，为缩短算法的时间，所以我们需要尽量甚至完全做到不创建新的节点，而原题没要求不能影响输入参数（此处应有滑稽），因而通过更改输入参数再将其输出来实现算法。

实现代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int flag = 0;
        int val = 0;
        ListNode* head1 = l1;
        ListNode* head2 = l2;
        ListNode* p1;
        ListNode* p2;
        ListNode* temp;
        
        while(l1!=NULL&&l2!=NULL)
        {
            val = l1->val+l2->val;
            
            l1->val = val;
            l2->val = val;
            p1 = l1;
            p2 = l2;
            l1 = l1->next;
            l2 = l2->next;
        }
	/**
	*  默认最长链表为l1，若l2较长则将它们交换
	*/
        if(l2!=NULL&&l1==NULL)
    	{
    	    temp = l1;
    	    l1 = l2;
            l2 = temp;
    	    temp = head1;
    	    head1 = head2;
    	    head2 = head1;
    	    temp = p1;
    	    p1 = p2;
    	    p2 = temp;
    	}
	/**
	*  做进位判断
	*/
       l1 = head1;
       while(l1!=NULL)
       {
           val = l1->val + flag;
           flag = 0;
           if(val>9)
           {
               flag = 1;
               val = val - 10;
           }
           l1->val = val;
           p1 = l1;
           l1 = l1->next;
       }
       if (flag==1)
       {
           p2->val = flag;
           p1->next = p2;
       }
       return head1;
   
    }
};

运行时间：32ms