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

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

本文概述

给定由两个链表表示的两个数字, 编写一个返回求和表的函数。求和列表是两个输入数字相加的链表表示。不允许修改列表。另外, 不允许使用显式的额外空间(提示：使用递归)。

例子

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)计算进位总和(在上一步中计算)与较大列表的剩余左子列表。此总和的节点将添加到上一步获得的总和列表的开头。

以下是上述方法的模拟：

将两个数字相加，以链表表示|S2

下图是上述方法的实现。

C ++

// A C++ recursive program to add two linked lists 
#include <bits/stdc++.h>
using namespace std;
  
// A linked List Node 
class Node 
{ 
     public :
     int data; 
     Node* next; 
}; 
  
typedef Node node; 
  
/* A utility function to insert 
a node at the beginning of linked list */
void push(Node** head_ref, int new_data) 
{ 
     /* 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 */
     new_node->next = (*head_ref); 
  
     /* move the head to point to the new node */
     (*head_ref) = 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; 
} 
  
// Adds two linked lists of same size 
// represented by head1 and head2 and returns 
// head of the resultant linked list. Carry
// is propagated while returning from the recursion 
node* addSameSize(Node* head1, Node* head2, int * carry) 
{ 
     // Since the function assumes linked lists are of same size, // check any of the two head pointers 
     if (head1 == NULL) 
         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 
     result->next = addSameSize(head1->next, head2->next, carry); 
  
     // add digits of current nodes and propagated carry 
     sum = head1->data + head2->data + *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. 
void addCarryToRemaining(Node* head1, Node* cur, int * carry, Node** result) 
{ 
     int sum; 
  
     // If diff. number of nodes are not traversed, add carry 
     if (head1 != cur) 
     { 
         addCarryToRemaining(head1->next, cur, carry, result); 
  
         sum = head1->data + *carry; 
         *carry = sum/10; 
         sum %= 10; 
  
         // add this node to the front of the result 
         push(result, sum); 
     } 
} 
  
// The main function that adds two linked lists 
// represented by head1 and head2. The sum of 
// two lists is stored in a list referred by result 
void addList(Node* head1, Node* head2, Node** result) 
{ 
     Node *cur; 
  
     // first list is empty 
     if (head1 == NULL) 
     { 
         *result = head2; 
         return ; 
     } 
  
     // second list is empty 
     else if (head2 == NULL) 
     { 
         *result = head1; 
         return ; 
     } 
  
     int size1 = getSize(head1); 
     int size2 = getSize(head2) ; 
  
     int carry = 0; 
  
     // Add same size lists 
     if (size1 == size2) 
         *result = addSameSize(head1, head2, &carry); 
  
     else
     { 
         int diff = abs (size1 - size2); 
  
         // First list should always be larger than second list. 
         // If not, swap pointers 
         if (size1 < size2) 
             swapPointer(&head1, &head2); 
  
         // move diff. number of nodes in first list 
         for (cur = head1; diff--; cur = cur->next); 
  
         // get addition of same size lists 
         *result = addSameSize(cur, head2, &carry); 
  
         // get addition of remaining first list and carry 
         addCarryToRemaining(head1, cur, &carry, result); 
     } 
  
     // 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() 
{ 
     Node *head1 = NULL, *head2 = NULL, *result = NULL; 
  
     int arr1[] = {9, 9, 9}; 
     int arr2[] = {1, 8}; 
  
     int size1 = sizeof (arr1) / sizeof (arr1[0]); 
     int size2 = sizeof (arr2) / sizeof (arr2[0]); 
  
     // Create first list as 9->9->9 
     int i; 
     for (i = size1-1; i >= 0; --i) 
         push(&head1, arr1[i]); 
  
     // Create second list as 1->8 
     for (i = size2-1; i >= 0; --i) 
         push(&head2, arr2[i]); 
  
     addList(head1, head2, &result); 
  
     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>
  
// A linked List Node
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 */
     new_node->next = (*head_ref);
  
     /* move the head to point to the new node */
     (*head_ref)    = 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;
}
  
// Adds two linked lists of same size represented by head1 and head2 and returns
// head of the resultant linked list. Carry is propagated while returning from
// the recursion
node* addSameSize(Node* head1, Node* head2, int * carry)
{
     // Since the function assumes linked lists are of same size, // check any of the two head pointers
     if (head1 == NULL)
         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
     result->next = addSameSize(head1->next, head2->next, carry);
  
     // add digits of current nodes and propagated carry
     sum = head1->data + head2->data + *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.
void addCarryToRemaining(Node* head1, Node* cur, int * carry, Node** result)
{
     int sum;
  
     // If diff. number of nodes are not traversed, add carry
     if (head1 != cur)
     {
         addCarryToRemaining(head1->next, cur, carry, result);
  
         sum = head1->data + *carry;
         *carry = sum/10;
         sum %= 10;
  
         // add this node to the front of the result
         push(result, sum);
     }
}
  
// The main function that adds two linked lists represented by head1 and head2.
// The sum of two lists is stored in a list referred by result
void addList(Node* head1, Node* head2, Node** result)
{
     Node *cur;
  
     // first list is empty
     if (head1 == NULL)
     {
         *result = head2;
         return ;
     }
  
     // second list is empty
     else if (head2 == NULL)
     {
         *result = head1;
         return ;
     }
  
     int size1 = getSize(head1);
     int size2 = getSize(head2) ;
  
     int carry = 0;
  
     // Add same size lists
     if (size1 == size2)
         *result = addSameSize(head1, head2, &carry);
  
     else
     {
         int diff = abs (size1 - size2);
  
         // First list should always be larger than second list.
         // If not, swap pointers
         if (size1 < size2)
             swapPointer(&head1, &head2);
  
         // move diff. number of nodes in first list
         for (cur = head1; diff--; cur = cur->next);
  
         // get addition of same size lists
         *result = addSameSize(cur, head2, &carry);
  
         // get addition of remaining first list and carry
         addCarryToRemaining(head1, cur, &carry, result);
     }
  
     // 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()
{
     Node *head1 = NULL, *head2 = NULL, *result = NULL;
  
     int arr1[] = {9, 9, 9};
     int arr2[] = {1, 8};
  
     int size1 = sizeof (arr1) / sizeof (arr1[0]);
     int size2 = sizeof (arr2) / sizeof (arr2[0]);
  
     // Create first list as 9->9->9
     int i;
     for (i = size1-1; i >= 0; --i)
         push(&head1, arr1[i]);
  
     // Create second list as 1->8
     for (i = size2-1; i >= 0; --i)
         push(&head2, arr2[i]);
  
     addList(head1, head2, &result);
  
     printList(result);
  
     return 0;
}

Java

// Java program to add two linked lists
  
public class linkedlistATN 
{
     class node 
     {
         int val;
         node next;
  
         public node( int val) 
         {
             this .val = val;
         }
     }
      
     // Function to print linked list
     void printlist(node head) 
     {
         while (head != null ) 
         {
             System.out.print(head.val + " " );
             head = head.next;
         }
     }
  
     node head1, head2, result;
     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 ) 
         {
             newnode.next = head1;
             head1 = newnode;
         } 
         else if (list == 2 ) 
         {
             newnode.next = head2;
             head2 = newnode;
         } 
         else 
         {
             newnode.next = result;
             result = newnode;
         }
  
     }
  
     // Adds two linked lists of same size represented by
     // head1 and head2 and returns head of the resultant 
     // linked list. Carry is propagated while returning 
     // from the recursion
     void addsamesize(node n, node m) 
     {
         // 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
         addsamesize(n.next, m.next);
  
         // 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.
     void propogatecarry(node head1) 
     {
         // If diff. number of nodes are not traversed, add carry
         if (head1 != cur) 
         {
             propogatecarry(head1.next);
             int sum = carry + head1.val;
             carry = sum / 10 ;
             sum %= 10 ;
  
             // add this node to the front of the result
             push(sum, 3 );
         }
     }
  
     int getsize(node head) 
     {
         int count = 0 ;
         while (head != null ) 
         {
             count++;
             head = head.next;
         }
         return count;
     }
  
     // The main function that adds two linked lists 
     // represented by head1 and head2. The sum of two 
     // lists is stored in a list referred by result
     void addlists() 
     {
         // first list is empty
         if (head1 == null ) 
         {
             result = head2;
             return ;
         }
  
         // first list is empty
         if (head2 == null ) 
         {
             result = head1;
             return ;
         }
  
         int size1 = getsize(head1);
         int size2 = getsize(head2);
  
         // Add same size lists
         if (size1 == size2) 
         {
             addsamesize(head1, head2);
         } 
         else 
         {
             // First list should always be larger than second list.
             // If not, swap pointers
             if (size1 < size2) 
             {
                 node temp = head1;
                 head1 = head2;
                 head2 = temp;
             }
             int diff = Math.abs(size1 - size2);
  
             // move diff. number of nodes in first list
             node temp = head1;
             while (diff-- >= 0 ) 
             {
                 cur = temp;
                 temp = temp.next;
             }
  
             // get addition of same size lists
             addsamesize(cur, head2);
  
             // get addition of remaining first list and carry
             propogatecarry(head1);
         }
             // 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[])
     {
         linkedlistATN list = new linkedlistATN();
         list.head1 = null ;
         list.head2 = null ;
         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.addlists();
  
         list.printlist(list.result);
     }
}
  
// This code is contributed by Rishabh Mahrsee

输出如下：

1  0  1  7

时间复杂度：O(m + n), 其中m和n是给定两个链表的大小。

相关文章：将两个数字相加, 以链表表示|套装1

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: