给定由两个列表表示的两个数字，编写一个返回求和列表的函数。总和列表是两个输入数字相加的列表表示。
null
实例 :
输入： 清单1:5->6->3//代表数字563 清单2:8->4->2//表示数字842 输出： 结果列表：1->4->0->5//代表数字1405 说明： 563 + 842 = 1405
输入： 列表1:7->5->9->4->6//代表数字75946 清单2:8->4//表示数字84 输出： 结果列表：7->6->0->3->0//代表数字76030 说明： 75946+84=76030
方法 ：将两个列表遍历到末尾，并在列表中添加前面的零（数字较小）。然后在两个列表的开始节点上调用一个递归函数，该函数为两个列表的下一个节点调用自己，直到到达结束。此函数为当前数字的和创建一个节点，并返回进位。
这些步骤是：
- 遍历两个链表，以便在一个链表的位数小于另一个链表的情况下添加前面的零。
- 从两个列表的头节点开始，为下一个节点调用递归函数。
- 继续，直到列表结束。
- 为当前数字和创建一个节点，并返回进位。
下面是这种方法的实现。
C++
// C++ program to add two numbers // represented by linked list #include <bits/stdc++.h> using namespace std; /* Linked list node */ class Node { public : int data; Node* next; }; /* Function to create a new node with given data */ Node* newNode( int data) { Node* new_node = new Node(); new_node->data = data; new_node->next = NULL; return new_node; } /* Function to insert a node at the beginning of the Singly Linked List */ void push(Node** head_ref, int new_data) { /* allocate node */ Node* new_node = newNode(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; } /* Adds contents of two linked lists and return the head node of resultant list */ Node* addTwoLists(Node* first, Node* second) { // res is head node of the resultant list Node* res = NULL; Node *temp, *prev = NULL; int carry = 0, sum; // while both lists exist while (first != NULL || second != NULL) { // Calculate value of next // digit in resultant list. // The next digit is sum of // following things // (i) Carry // (ii) Next digit of first // list (if there is a next digit) // (ii) Next digit of second // list (if there is a next digit) sum = carry + (first ? first->data : 0) + (second ? second->data : 0); // update carry for next calculation carry = (sum >= 10) ? 1 : 0; // update sum if it is greater than 10 sum = sum % 10; // Create a new node with sum as data temp = newNode(sum); // if this is the first node then // set it as head of the resultant list if (res == NULL) res = temp; // If this is not the first // node then connect it to the rest. else prev->next = temp; // Set prev for next insertion prev = temp; // Move first and second // pointers to next nodes if (first) first = first->next; if (second) second = second->next; } if (carry > 0) temp->next = newNode(carry); // return head of the resultant list return res; } Node* reverse(Node* head) { if (head == NULL || head->next == NULL) return head; /* reverse the rest list and put the first element at the end */ Node* rest = reverse(head->next); head->next->next = head; head->next = NULL; /* fix the head pointer */ return rest; } // A utility function to print a linked list void printList(Node* node) { while (node != NULL) { cout << node->data << " " ; node = node->next; } cout << endl; } /* Driver code */ int main( void ) { Node* res = NULL; Node* first = NULL; Node* second = NULL; // create first list 7->5->9->4->6 push(&first, 6); push(&first, 4); push(&first, 9); push(&first, 5); push(&first, 7); printf ( "First List is " ); printList(first); // create second list 8->4 push(&second, 4); push(&second, 8); cout << "Second List is " ; printList(second); // reverse both the lists first = reverse(first); second = reverse(second); // Add the two lists res = addTwoLists(first, second); // reverse the res to get the sum res = reverse(res); cout << "Resultant list is " ; printList(res); return 0; } |
C
#include <stdio.h> #include <stdlib.h> /* Linked list node */ struct Node { int data; struct Node* next; }; /* Function to create a new node with given data */ struct Node* newNode( int data) { struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); new_node->data = data; new_node->next = NULL; return new_node; } /* Function to insert a node at the beginning of the Singly Linked List */ void push( struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = newNode(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; } /* Adds contents of two linked lists and return the head node of resultant list */ struct Node* addTwoLists( struct Node* first, struct Node* second) { // res is head node of the resultant list struct Node* res = NULL; struct Node *temp, *prev = NULL; int carry = 0, sum; // while both lists exist while (first != NULL || second != NULL) { // Calculate value of next // digit in resultant list. // The next digit is sum // of following things // (i) Carry // (ii) Next digit of first // list (if there is a next digit) // (ii) Next digit of second // list (if there is a next digit) sum = carry + (first ? first->data : 0) + (second ? second->data : 0); // Update carry for next calculation carry = (sum >= 10) ? 1 : 0; // Update sum if it is greater than 10 sum = sum % 10; // Create a new node with sum as data temp = newNode(sum); // if this is the first node then // set it as head of the resultant list if (res == NULL) res = temp; // If this is not the first node // then connect it to the rest. else prev->next = temp; // Set prev for next insertion prev = temp; // Move first and second // pointers to next nodes if (first) first = first->next; if (second) second = second->next; } if (carry > 0) temp->next = newNode(carry); // return head of the resultant list return res; } // A utility function to print a linked list void printList( struct Node* node) { while (node != NULL) { printf ( "%d " , node->data); node = node->next; } printf ( "" ); } /* Driver code */ int main( void ) { struct Node* res = NULL; struct Node* first = NULL; struct Node* second = NULL; // create first list 7->5->9->4->6 push(&first, 6); push(&first, 4); push(&first, 9); push(&first, 5); push(&first, 7); printf ( "First List is " ); printList(first); // create second list 8->4 push(&second, 4); push(&second, 8); printf ( "Second List is " ); printList(second); // Add the two lists and see result res = addTwoLists(first, second); printf ( "Resultant list is " ); printList(res); return 0; } |
JAVA
// Java program to add two numbers // represented by linked list class LinkedList { static Node head1, head2; static class Node { int data; Node next; Node( int d) { data = d; next = null ; } } /* Adds contents of two linked lists and prints it */ void addTwoLists(Node first, Node second) { Node start1 = new Node( 0 ); start1.next = first; Node start2 = new Node( 0 ); start2.next = second; addPrecedingZeros(start1, start2); Node result = new Node( 0 ); if (sumTwoNodes(start1.next, start2.next, result) == 1 ) { Node node = new Node( 1 ); node.next = result.next; result.next = node; } printList(result.next); } /* Adds lists and returns the carry */ private int sumTwoNodes(Node first, Node second, Node result) { if (first == null ) { return 0 ; } int number = first.data + second.data + sumTwoNodes(first.next, second.next, result); Node node = new Node(number % 10 ); node.next = result.next; result.next = node; return number / 10 ; } /* Appends preceding zeros in case a list is having lesser nodes than the other one*/ private void addPrecedingZeros(Node start1, Node start2) { Node next1 = start1.next; Node next2 = start2.next; while (next1 != null && next2 != null ) { next1 = next1.next; next2 = next2.next; } if (next1 == null && next2 != null ) { while (next2 != null ) { Node node = new Node( 0 ); node.next = start1.next; start1.next = node; next2 = next2.next; } } else if (next2 == null && next1 != null ) { while (next1 != null ) { Node node = new Node( 0 ); node.next = start2.next; start2.next = node; next1 = next1.next; } } } /* Utility function to print a linked list */ void printList(Node head) { while (head != null ) { System.out.print(head.data + " " ); head = head.next; } System.out.println( "" ); } // Driver Code public static void main(String[] args) { LinkedList list = new LinkedList(); // creating first list list.head1 = new Node( 7 ); list.head1.next = new Node( 5 ); list.head1.next.next = new Node( 9 ); list.head1.next.next.next = new Node( 4 ); list.head1.next.next.next.next = new Node( 6 ); System.out.print( "First List is " ); list.printList(head1); // creating second list list.head2 = new Node( 8 ); list.head2.next = new Node( 4 ); System.out.print( "Second List is " ); list.printList(head2); System.out.print( "Resultant List is " ); // add the two lists and see the result list.addTwoLists(head1, head2); } // this code is contributed by *Saurabh321Gupta* } |
Python3
# Python program to add two numbers represented by linked list # Node class class Node: # Constructor to initialize the node object def __init__( self , data): self .data = data self . next = None class LinkedList: # Function to initialize head def __init__( self ): self .head = None # Function to insert a new node at the beginning def push( self , new_data): new_node = Node(new_data) new_node. next = self .head self .head = new_node # Add contents of two linked lists and return the head # node of resultant list def addTwoLists( self , first, second): prev = None temp = None carry = 0 # While both list exists while (first is not None or second is not None ): # Calculate the value of next digit in # resultant list # The next digit is sum of following things # (i) Carry # (ii) Next digit of first list (if ther is a # next digit) # (iii) Next digit of second list ( if there # is a next digit) fdata = 0 if first is None else first.data sdata = 0 if second is None else second.data Sum = carry + fdata + sdata # update carry for next calculation carry = 1 if Sum > = 10 else 0 # update sum if it is greater than 10 Sum = Sum if Sum < 10 else Sum % 10 # Create a new node with sum as data temp = Node( Sum ) # if this is the first node then set it as head # of resultant list if self .head is None : self .head = temp else : prev. next = temp # Set prev for next insertion prev = temp # Move first and second pointers to next nodes if first is not None : first = first. next if second is not None : second = second. next if carry > 0 : temp. next = Node(carry) # Utility function to print the LinkedList def printList( self ): temp = self .head while (temp): print (temp.data,end = ' ' ) temp = temp. next # Driver code first = LinkedList() second = LinkedList() # Create first list first.push( 6 ) first.push( 4 ) first.push( 9 ) first.push( 5 ) first.push( 7 ) print ( "First List is " ,end = ' ' ) first.printList() # Create second list second.push( 4 ) second.push( 8 ) print ( "Second List is" ,end = ' ' ) second.printList() # Add the two lists and see result res = LinkedList() res.addTwoLists(first.head, second.head) print ( "Resultant list is" ,end = ' ' ) res.printList() # This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
C#
// C# program to add two numbers // represented by linked list using System; public class LinkedList { Node head1, head2; public class Node { public int data; public Node next; public Node( int d) { data = d; next = null ; } } /* Adds contents of two linked lists and return the head node of resultant list */ Node addTwoLists(Node first, Node second) { // res is head node of the resultant list Node res = null ; Node prev = null ; Node temp = null ; int carry = 0, sum; // while both lists exist while (first != null || second != null ) { // Calculate value of next digit in resultant // list. The next digit is sum of following // things (i) Carry (ii) Next digit of first // list (if there is a next digit) (ii) Next // digit of second list (if there is a next // digit) sum = carry + (first != null ? first.data : 0) + (second != null ? second.data : 0); // update carry for next calculation carry = (sum >= 10) ? 1 : 0; // update sum if it is greater than 10 sum = sum % 10; // Create a new node with sum as data temp = new Node(sum); // if this is the first node then set it as head // of the resultant list if (res == null ) { res = temp; } // If this is not the first // node then connect it to the rest. else { prev.next = temp; } // Set prev for next insertion prev = temp; // Move first and second pointers to next nodes if (first != null ) { first = first.next; } if (second != null ) { second = second.next; } } if (carry > 0) { temp.next = new Node(carry); } // return head of the resultant list return res; } /* Utility function to print a linked list */ void printList(Node head) { while (head != null ) { Console.Write(head.data + " " ); head = head.next; } Console.WriteLine( "" ); } // Driver code public static void Main(String[] args) { LinkedList list = new LinkedList(); // creating first list list.head1 = new Node(7); list.head1.next = new Node(5); list.head1.next.next = new Node(9); list.head1.next.next.next = new Node(4); list.head1.next.next.next.next = new Node(6); Console.Write( "First List is " ); list.printList(list.head1); // creating second list list.head2 = new Node(8); list.head2.next = new Node(4); Console.Write( "Second List is " ); list.printList(list.head2); // add the two lists and see the result Node rs = list.addTwoLists(list.head1, list.head2); Console.Write( "Resultant List is " ); list.printList(rs); } } // This code contributed by Rajput-Ji |
Javascript
<script> // Javascript program to add two numbers // represented by linked list var head1, head2; class Node { constructor(val) { this .data = val; this .next = null ; } } /* Adds contents of two linked lists and return the head node of resultant list */ function addTwoLists( first, second) { // res is head node of the resultant list var res = null ; var prev = null ; var temp = null ; var carry = 0, sum; // while both lists exist while (first != null || second != null ) { // Calculate value of next // digit in resultant list. // The next digit is sum // of following things // (i) Carry // (ii) Next digit of first // list (if there is a next digit) // (ii) Next digit of second // list (if there is a next digit) sum = carry + (first != null ? first.data : 0) + (second != null ? second.data : 0); // update carry for next calculation carry = (sum >= 10) ? 1 : 0; // update sum if it is greater than 10 sum = sum % 10; // Create a new node with sum as data temp = new Node(sum); // if this is the first node then set // it as head of the resultant list if (res == null ) { res = temp; } // If this is not the first // node then connect it to the rest. else { prev.next = temp; } // Set prev for next insertion prev = temp; // Move first and second pointers // to next nodes if (first != null ) { first = first.next; } if (second != null ) { second = second.next; } } if (carry > 0) { temp.next = new Node(carry); } // return head of the resultant list return res; } /* Utility function to print a linked list */ function printList( head) { while (head != null ) { document.write(head.data + " " ); head = head.next; } document.write( "<br/>" ); } // Driver Code // creating first list head1 = new Node(7); head1.next = new Node(5); head1.next.next = new Node(9); head1.next.next.next = new Node(4); head1.next.next.next.next = new Node(6); document.write( "First List is " ); printList(head1); // creating second list head2 = new Node(8); head2.next = new Node(4); document.write( "Second List is " ); printList(head2); // add the two lists and see the result rs = addTwoLists(head1, head2); document.write( "Resultant List is " ); printList(rs); // This code contributed by aashish1995 </script> |
输出
First List is 7 5 9 4 6 Second List is 8 4 Resultant list is 5 0 0 5 6
复杂性分析：
- 时间复杂性： O（m+n），其中m和n分别是第一个和第二个列表中的节点数。 这些列表只需要遍历一次。
- 空间复杂性： O（m+n）。 需要一个临时链表来存储输出编号
方法2（使用STL）： 使用堆栈数据结构
方法：
- 创建3个堆栈，即s1、s2、s3。
- 用列表1的节点填充s1，用列表2的节点填充s2。
- 通过创建新节点并将新节点的数据设置为s1之和来填充s3。top（），s2。top（）并继续，直到列表1和列表2为空。
- 如果总和>9
- 一套一套
- 其他的
- 设定进位0
- 创建一个节点（比如prev），该节点将包含总和列表的开头。
- 从上到下链接s3的所有元素
- 返回上一个
代码：
C++
// C++ program to add two numbers represented by Linked // Lists using Stack #include <bits/stdc++.h> using namespace std; class Node { public : int data; Node* next; }; Node* newnode( int data) { Node* x = new Node(); x->data = data; return x; } // function that returns the sum of two numbers represented // by linked lists Node* addTwoNumbers(Node* l1, Node* l2) { Node* prev = NULL; // Create 3 stacks stack<Node*> s1, s2, s3; // Fill first stack with first List Elements while (l1 != NULL) { s1.push(l1); l1 = l1->next; } // Fill second stack with second List Elements while (l2 != NULL) { s2.push(l2); l2 = l2->next; } int carry = 0; // Fill the third stack with the sum of first and second // stack while (!s1.empty() && !s2.empty()) { int sum = s1.top()->data + s2.top()->data + carry; Node* temp = newnode(sum % 10); s3.push(temp); if (sum > 9) { carry = 1; } else { carry = 0; } s1.pop(); s2.pop(); } while (!s1.empty()) { int sum = carry + s1.top()->data; Node* temp = newnode(sum % 10); s3.push(temp); if (sum > 9) { carry = 1; } else { carry = 0; } s1.pop(); } while (!s2.empty()) { int sum = carry + s2.top()->data; Node* temp = newnode(sum % 10); s3.push(temp); if (sum > 9) { carry = 1; } else { carry = 0; } s2.pop(); } // If carry is still present create a new node with // value 1 and push it to the third stack if (carry == 1) { Node* temp = newnode(1); s3.push(temp); } // Link all the elements inside third stack with each // other if (!s3.empty()) prev = s3.top(); while (!s3.empty()) { Node* temp = s3.top(); s3.pop(); if (s3.size() == 0) { temp->next = NULL; } else { temp->next = s3.top(); } } return prev; } // utility functions // Function that displays the List void Display(Node* head) { if (head == NULL) { return ; } while (head->next != NULL) { cout << head->data << " -> " ; head = head->next; } cout << head->data << endl; } // Function that adds element at the end of the Linked List void push(Node** head_ref, int d) { Node* new_node = newnode(d); new_node->next = NULL; if (*head_ref == NULL) { new_node->next = *head_ref; *head_ref = new_node; return ; } Node* last = *head_ref; while (last->next != NULL && last != NULL) { last = last->next; } last->next = new_node; return ; } // Driver Program for above Functions int main() { // Creating two lists // first list = 9 -> 5 -> 0 // second List = 6 -> 7 Node* first = NULL; Node* second = NULL; Node* sum = NULL; push(&first, 9); push(&first, 5); push(&first, 0); push(&second, 6); push(&second, 7); cout << "First List : " ; Display(first); cout << "Second List : " ; Display(second); sum = addTwoNumbers(first, second); cout << "Sum List : " ; Display(sum); return 0; } |
输出
First List : 9 -> 5 -> 0Second List : 6 -> 7Sum List : 1 -> 0 -> 1 -> 7
另一种时间复杂度为O（N）的方法：
给定方法的工作步骤如下：
- 首先，我们分别计算链表size1和size2的大小。
- 然后我们遍历更大的链表（如果有的话），然后递减，直到两者的大小相同。
- 现在我们遍历两个链表，直到最后。
- 现在，执行加法时会发生回溯。
- 最后，head节点返回到包含答案的链表。
C++
#include <iostream> using namespace std; struct Node { int data; struct Node* next; }; // recursive function Node* addition(Node* temp1, Node* temp2, int size1, int size2) { // creating a new Node Node* newNode = ( struct Node*) malloc ( sizeof ( struct Node)); // base case if (temp1->next == NULL && temp2->next == NULL) { // addition of current nodes which is the last nodes // of both linked lists newNode->data = (temp1->data + temp2->data); // set this current node's link null newNode->next = NULL; // return the current node return newNode; } // creating a node that contains sum of previously added // number Node* returnedNode = ( struct Node*) malloc ( sizeof ( struct Node)); // if sizes are same then we move in both linked list if (size2 == size1) { // recursively call the function // move ahead in both linked list returnedNode = addition(temp1->next, temp2->next, size1 - 1, size2 - 1); // add the current nodes and append the carry newNode->data = (temp1->data + temp2->data) + ((returnedNode->data) / 10); } // or else we just move in big linked list else { // recursively call the function // move ahead in big linked list returnedNode = addition(temp1, temp2->next, size1, size2 - 1); // add the current node and carry newNode->data = (temp2->data) + ((returnedNode->data) / 10); } // this node contains previously added numbers // so we need to set only rightmost digit of it returnedNode->data = (returnedNode->data) % 10; // set the returned node to the current node newNode->next = returnedNode; // return the current node return newNode; } // Function to add two numbers represented by nexted list. struct Node* addTwoLists( struct Node* head1, struct Node* head2) { struct Node *temp1, *temp2, *ans = NULL; temp1 = head1; temp2 = head2; int size1 = 0, size2 = 0; // calculating the size of first linked list while (temp1 != NULL) { temp1 = temp1->next; size1++; } // calculating the size of second linked list while (temp2 != NULL) { temp2 = temp2->next; size2++; } Node* returnedNode = ( struct Node*) malloc ( sizeof ( struct Node)); // traverse the bigger linked list if (size2 > size1) { returnedNode = addition(head1, head2, size1, size2); } else { returnedNode = addition(head2, head1, size2, size1); } // creating new node if head node is >10 if (returnedNode->data >= 10) { ans = ( struct Node*) malloc ( sizeof ( struct Node)); ans->data = (returnedNode->data) / 10; returnedNode->data = returnedNode->data % 10; ans->next = returnedNode; } else ans = returnedNode; // return the head node of linked list that contains // answer return ans; } void Display(Node* head) { if (head == NULL) { return ; } while (head->next != NULL) { cout << head->data << " -> " ; head = head->next; } cout << head->data << endl; } // Function that adds element at the end of the Linked List void push(Node** head_ref, int d) { Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); new_node->data = d; new_node->next = NULL; if (*head_ref == NULL) { new_node->next = *head_ref; *head_ref = new_node; return ; } Node* last = *head_ref; while (last->next != NULL && last != NULL) { last = last->next; } last->next = new_node; return ; } // Driver Program for above Functions int main() { // Creating two lists Node* first = NULL; Node* second = NULL; Node* sum = NULL; push(&first, 5); push(&first, 6); push(&first, 3); push(&second, 8); push(&second, 4); push(&second, 2); cout << "First List : " ; Display(first); cout << "Second List : " ; Display(second); sum = addTwoLists(first, second); cout << "Sum List : " ; Display(sum); return 0; } // This code is contributed by Dharmik Parmar |
输出
First List : 5 -> 6 -> 3Second List : 8 -> 4 -> 2Sum List : 1 -> 4 -> 0 -> 5
相关文章： 添加两个由链表表示的数字|集合2
如果您发现上述代码/算法不正确，请写下评论，或者寻找其他方法来解决相同的问题。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
