LeetCode_Add Two Numbers

题目：

You are given two linked lists representing two non-negative numbers. 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.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

思路：计算进位，注意最后一位的处理。

#include<iostream>

using namespace std;

struct ListNode {

      int val;

      ListNode *next;

      ListNode(int x) : val(x), next(NULL) {}

};

ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)

{

	  if(l1 == NULL || l2 == NULL)

	  {

	  	return l1==NULL?l2:l1;

	  }

	  ListNode *head = l1;

	  int len1 = 0;

	  int len2 = 0;

	  ListNode *p1 = l1;

	  ListNode *p2 = l2;

	  while(p1!=NULL)

	  {

	  	len1++;

	  	p1=p1->next;

	  }

	  while(p2!=NULL)

	  {

	  	len2++;

	  	p2=p2->next;

	  }

	  //cout<<len1<<";"<<len2<<endl;

	  ListNode *pre_l1 = l1;

	  ListNode *pre_l2 = l2; 

	  int jinwei = 0;

	  while(l1!=NULL && l2!=NULL)

	  {

	  	int sum = l1->val + l2->val + jinwei;

	  	l1->val = sum%10;

	  	//计算进位

	  	if(sum>=10)

	  	{

	  		jinwei = 1;

		}

		else

		{

			jinwei = 0;

		}

		pre_l1 = l1;

		l1 = l1->next;

		pre_l2 = l2;

		l2 = l2->next;

	  }

	  if(l1==NULL&&l2!=NULL)

	  {

	  	pre_l1->next = l2;

	  	while(l1==NULL&&l2!=NULL)

	  	{

	  		int sum = l2->val + jinwei;

	  		l2->val = sum%10;

	  		if(sum>=10)

	  		{

	  			jinwei = 1;

			}

			else

			{

				jinwei = 0;

			}

			pre_l2 = l2;

			l2 = l2->next;

	  	}

	  }

	  if(l2==NULL&&l1!=NULL)

	  {

	  	while(l2==NULL&&l1!=NULL)

	  	{

	  		int sum = l1->val + jinwei;

	  		l1->val = sum%10;

	  		if(sum>=10)

	  		{

	  			jinwei = 1;

			}

			else

			{

				jinwei = 0;

			}

			pre_l1 = l1;

			l1 = l1->next;

	  	}

	  }

	  if(jinwei == 1 && len1>=len2)

	  {

	  	ListNode *end = new ListNode(jinwei);

	  	//找到最后的节点

	  	pre_l1->next = end;

	  }

	  if(jinwei == 1 && len1<len2)

	  {

	  	ListNode *end = new ListNode(jinwei);

	  	//找到最后的节点

	  	pre_l2->next = end;

	  }

	  return head;

}

int main(void)

{

	//cout<<"l"<<endl;

	ListNode *l1 = new ListNode(2);

	ListNode *l2 = new ListNode(4);

	ListNode *l3 = new ListNode(3);

	l1->next = l2;

	l2->next = l3;

	ListNode *l11 = new ListNode(5);

	ListNode *l21 = new ListNode(6);

	ListNode *l31 = new ListNode(2);

	l11->next = l21;

	l21->next = l31;

	ListNode *p = addTwoNumbers(l1,l11);

	while(p!=NULL)

	{

		cout<<p->val<<" ";

		p=p->next;

	}

	delete l1;

	delete l2;

	delete l3;

	delete l11;

	delete l21;

	delete l31;

	system("pause");

	return 0;

}

巴特西

LeetCode_Add Two Numbers

最新文章

热门文章