# 算法题：将两个数字相加，使用链表表示|S2

2021年3月25日12:37:43 发表评论 329 次浏览

## 本文概述

``````Input:
First List: 5->6->3  // represents number 563
Second List: 8->4->2 //  represents number 842
Output
Resultant list: 1->4->0->5  // represents number 1405``````

1)计算给定两个链表的大小。

2)如果大小相同, 则使用递归计算总和。将所有节点保留在递归调用堆栈中, 直到最右边的节点, 计算最右边的节点的总和, 然后再进位到左边。

3)如果大小不相同, 请执行以下步骤：

...a)计算两个链表大小的差。让差为diff

...b)在较大的链表中向前移动diff节点。现在使用步骤2来计算小列表和大列表的右子列表(相同大小)的总和。同时，存储这个总和的进位

...c)计算进位总和(在上一步中计算)与较大列表的剩余左子列表。此总和的节点将添加到上一步获得的总和列表的开头。

## C ++

``````// A C++ recursive program to add two linked lists
#include <bits/stdc++.h>
using namespace std;

class Node
{
public :
int data;
Node* next;
};

typedef Node node;

/* A utility function to insert
a node at the beginning of linked list */
{
/* allocate node */
Node* new_node = new Node[( sizeof (Node))];

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */

/* move the head to point to the new node */
}

/* A utility function to print linked list */
void printList(Node *node)
{
while (node != NULL)
{
cout<<node->data<< " " ;
node = node->next;
}
cout<<endl;
}

// A utility function to swap two pointers
void swapPointer( Node** a, Node** b )
{
node* t = *a;
*a = *b;
*b = t;
}

/* A utility function to get size of linked list */
int getSize(Node *node)
{
int size = 0;
while (node != NULL)
{
node = node->next;
size++;
}
return size;
}

// is propagated while returning from the recursion
{
// Since the function assumes linked lists are of same size, // check any of the two head pointers
return NULL;

int sum;

// Allocate memory for sum node of current two nodes
Node* result = new Node[( sizeof (Node))];

// Recursively add remaining nodes and get the carry

// add digits of current nodes and propagated carry
*carry = sum / 10;
sum = sum % 10;

// Assigne the sum to current node of resultant list
result->data = sum;

return result;
}

// This function is called after the
// smaller list is added to the bigger
// lists's sublist of same size. Once the
// right sublist is added, the carry
// must be added toe left side of larger
// list to get the final result.
{
int sum;

// If diff. number of nodes are not traversed, add carry
{

*carry = sum/10;
sum %= 10;

// add this node to the front of the result
push(result, sum);
}
}

// two lists is stored in a list referred by result
{
Node *cur;

// first list is empty
{
return ;
}

// second list is empty
{
return ;
}

int carry = 0;

if (size1 == size2)

else
{
int diff = abs (size1 - size2);

// First list should always be larger than second list.
// If not, swap pointers
if (size1 < size2)

// move diff. number of nodes in first list
for (cur = head1; diff--; cur = cur->next);

// get addition of same size lists

// get addition of remaining first list and carry
}

// if some carry is still there, add a new node to the fron of
// the result list. e.g. 999 and 87
if (carry)
push(result, carry);
}

// Driver code
int main()
{

int arr1[] = {9, 9, 9};
int arr2[] = {1, 8};

int size1 = sizeof (arr1) / sizeof (arr1);
int size2 = sizeof (arr2) / sizeof (arr2);

// Create first list as 9->9->9
int i;
for (i = size1-1; i >= 0; --i)

// Create second list as 1->8
for (i = size2-1; i >= 0; --i)

printList(result);

return 0;
}

// This code is contributed by rathbhupendra``````

## C

``````// A recursive program to add two linked lists

#include <stdio.h>
#include <stdlib.h>

struct Node
{
int data;
struct Node* next;
};

typedef struct Node node;

/* A utility function to insert a node at the beginning of linked list */
void push( struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node));

/* put in the data  */
new_node->data  = new_data;

/* link the old list off the new node */

/* move the head to point to the new node */
}

/* A utility function to print linked list */
void printList( struct Node *node)
{
while (node != NULL)
{
printf ( "%d  " , node->data);
node = node->next;
}
printf ( "n" );
}

// A utility function to swap two pointers
void swapPointer( Node** a, Node** b )
{
node* t = *a;
*a = *b;
*b = t;
}

/* A utility function to get size of linked list */
int getSize( struct Node *node)
{
int size = 0;
while (node != NULL)
{
node = node->next;
size++;
}
return size;
}

// head of the resultant linked list. Carry is propagated while returning from
// the recursion
{
// Since the function assumes linked lists are of same size, // check any of the two head pointers
return NULL;

int sum;

// Allocate memory for sum node of current two nodes
Node* result = (Node *) malloc ( sizeof (Node));

// Recursively add remaining nodes and get the carry

// add digits of current nodes and propagated carry
*carry = sum / 10;
sum = sum % 10;

// Assigne the sum to current node of resultant list
result->data = sum;

return result;
}

// This function is called after the smaller list is added to the bigger
// lists's sublist of same size.  Once the right sublist is added, the carry
// must be added toe left side of larger list to get the final result.
{
int sum;

// If diff. number of nodes are not traversed, add carry
{

*carry = sum/10;
sum %= 10;

// add this node to the front of the result
push(result, sum);
}
}

// The sum of two lists is stored in a list referred by result
{
Node *cur;

// first list is empty
{
return ;
}

// second list is empty
{
return ;
}

int carry = 0;

if (size1 == size2)

else
{
int diff = abs (size1 - size2);

// First list should always be larger than second list.
// If not, swap pointers
if (size1 < size2)

// move diff. number of nodes in first list
for (cur = head1; diff--; cur = cur->next);

// get addition of same size lists

// get addition of remaining first list and carry
}

// if some carry is still there, add a new node to the fron of
// the result list. e.g. 999 and 87
if (carry)
push(result, carry);
}

// Driver program to test above functions
int main()
{

int arr1[] = {9, 9, 9};
int arr2[] = {1, 8};

int size1 = sizeof (arr1) / sizeof (arr1);
int size2 = sizeof (arr2) / sizeof (arr2);

// Create first list as 9->9->9
int i;
for (i = size1-1; i >= 0; --i)

// Create second list as 1->8
for (i = size2-1; i >= 0; --i)

printList(result);

return 0;
}``````

## Java

``````// Java program to add two linked lists

{
class node
{
int val;
node next;

public node( int val)
{
this .val = val;
}
}

// Function to print linked list
{
{
}
}

int carry;

/* A utility function to push a value to linked list */
void push( int val, int list)
{
node newnode = new node(val);
if (list == 1 )
{
}
else if (list == 2 )
{
}
else
{
newnode.next = result;
result = newnode;
}

}

// linked list. Carry is propagated while returning
// from the recursion
{
// Since the function assumes linked lists are of
// same size, check any of the two head pointers
if (n == null )
return ;

// Recursively add remaining nodes and get the carry

// add digits of current nodes and propagated carry
int sum = n.val + m.val + carry;
carry = sum / 10 ;
sum = sum % 10 ;

// Push this to result list
push(sum, 3 );

}

node cur;

// This function is called after the smaller list is
// added to the bigger lists's sublist of same size.
// Once the right sublist is added, the carry must be
// added to the left side of larger list to get the
// final result.
{
// If diff. number of nodes are not traversed, add carry
{
int sum = carry + head1.val;
carry = sum / 10 ;
sum %= 10 ;

// add this node to the front of the result
push(sum, 3 );
}
}

{
int count = 0 ;
{
count++;
}
return count;
}

// lists is stored in a list referred by result
{
// first list is empty
{
return ;
}

// first list is empty
{
return ;
}

if (size1 == size2)
{
}
else
{
// First list should always be larger than second list.
// If not, swap pointers
if (size1 < size2)
{
}
int diff = Math.abs(size1 - size2);

// move diff. number of nodes in first list
while (diff-- >= 0 )
{
cur = temp;
temp = temp.next;
}

// get addition of same size lists

// get addition of remaining first list and carry
}
// if some carry is still there, add a new node to
// the front of the result list. e.g. 999 and 87
if (carry > 0 )
push(carry, 3 );

}

// Driver program to test above functions
public static void main(String args[])
{
list.result = null ;
list.carry = 0 ;
int arr1[] = { 9 , 9 , 9 };
int arr2[] = { 1 , 8 };

// Create first list as 9->9->9
for ( int i = arr1.length - 1 ; i >= 0 ; --i)
list.push(arr1[i], 1 );

// Create second list as 1->8
for ( int i = arr2.length - 1 ; i >= 0 ; --i)
list.push(arr2[i], 2 );

list.printlist(list.result);
}
}

// This code is contributed by Rishabh Mahrsee``````

``1  0  1  7`` 