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

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

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; // 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 = https://www.lsbin.com/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 = https://www.lsbin.com/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

// 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= https://www.lsbin.com/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 = https://www.lsbin.com/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 listspublic 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

输出如下：