Given a number represented by a linked list, write a function that returns the sum of that number with its reverse form, and returns the resultant linked list.
Note: Avoid modifying the original linked list.
Examples:
Input: 1->2->3->4
Output: 5->5->5->5
Explanation:Input list: 1 2 3 4
Reverse list: + 4 3 2 1
resultant list: 5 5 5 5Input: 4->7->3->6
Output: 1->1->1->1->0
Explanation:Input list: 4 7 3 6
reverse list: + 6 3 7 4
resultant list: 1 1 1 1 0
Approach: The approach to solve the problem of adding linked lists and its reverse can be divided into the following steps:
- Make a copy of the given linked list: To avoid modifying the original linked list, a copy of it is created.
- Reverse the linked list: The reversed linked list is obtained by iteratively changing the next pointer of each node to point to the previous node.
- Add the linked list and its reverse: The two linked lists (original linked list and its reverse) are added digit by digit, starting from the least significant digit. A carry variable is maintained while adding the digits.
- Reverse the result of the addition: The result of the addition, which is in reverse order, is reversed back to obtain the final result.
- Print the resultant linked list: The final resultant linked list is printed.
Below is the implementation of this approach.
C++
// C++ code of above approach#include <bits/stdc++.h>using namespace std;// Define the structure of a// node in the linked liststruct Node { int data; struct Node* next; Node(int x) { data = x; next = NULL; }};// Function to return the// reverse of a linked listNode* reverseList(Node* head){ Node* prev = NULL; Node* cur = head; Node* next_ = NULL; while (cur != NULL) { next_ = cur->next; cur->next = prev; prev = cur; cur = next_; } return prev;}// Function to return the sum of two// linked listsNode* addTwoLists(Node* l1, Node* l2){ Node* dummy = new Node(0); Node* cur = dummy; int carry = 0; while (l1 != NULL || l2 != NULL) { int x = l1 ? l1->data : 0; int y = l2 ? l2->data : 0; int sum = carry + x + y; carry = sum / 10; cur->next = new Node(sum % 10); cur = cur->next; if (l1) { l1 = l1->next; } if (l2) { l2 = l2->next; } } if (carry > 0) { cur->next = new Node(carry); } return dummy->next;}// Function to print a linked listvoid printList(Node* head){ while (head != NULL) { cout << head->data << " "; head = head->next; } cout << endl;}// Function to create a copy of// a linked listNode* copyList(Node* head){ Node* cur = head; Node* dummy = new Node(0); Node* copy = dummy; while (cur != NULL) { copy->next = new Node(cur->data); copy = copy->next; cur = cur->next; } return dummy->next;}// Driver Codeint main(){ // Example linked list: // 1 -> 2 -> 3 -> 4 Node* head1 = new Node(1); head1->next = new Node(2); head1->next->next = new Node(3); head1->next->next->next = new Node(4); // Printing original linked list cout << "Original linked list : "; printList(head1); // Step1 - Make a copy of original // linked list Node* newList = copyList(head1); // Step2 - Reverse a linked list Node* head2 = reverseList(newList); // Printing reversed linked list cout << "Reversed linked list : "; printList(head2); // Step3 - Addition of a original // linked list and its reverse Node* addition = addTwoLists(head1, head2); // Step4 - Reverse a addition // Linked list Node* result = reverseList(addition); // Step5 - Print the resultant // linked list cout << "Resultant linked list : "; printList(result); return 0;} |
Java
// Java code implementation for the above approachimport java.io.*;import java.util.*;// Define the structure of a node in the linked listclass Node { int data; Node next; Node(int x) { data = x; next = null; }}class GFG { // Function to return the reverse of a linked list static Node reverseList(Node head) { Node prev = null; Node cur = head; Node next_; while (cur != null) { next_ = cur.next; cur.next = prev; prev = cur; cur = next_; } return prev; } // Function to return the sum of two linked lists static Node addTwoLists(Node l1, Node l2) { Node dummy = new Node(0); Node cur = dummy; int carry = 0; while (l1 != null || l2 != null) { int x = l1 != null ? l1.data : 0; int y = l2 != null ? l2.data : 0; int sum = carry + x + y; carry = sum / 10; cur.next = new Node(sum % 10); cur = cur.next; if (l1 != null) { l1 = l1.next; } if (l2 != null) { l2 = l2.next; } } if (carry > 0) { cur.next = new Node(carry); } return dummy.next; } // Function to print a linked list static void printList(Node head) { while (head != null) { System.out.print(head.data + " "); head = head.next; } System.out.println(); } // Function to create a copy of a linked list static Node copyList(Node head) { Node cur = head; Node dummy = new Node(0); Node copy = dummy; while (cur != null) { copy.next = new Node(cur.data); copy = copy.next; cur = cur.next; } return dummy.next; } public static void main(String[] args) { // Example linked list: // 1 -> 2 -> 3 -> 4 Node head1 = new Node(1); head1.next = new Node(2); head1.next.next = new Node(3); head1.next.next.next = new Node(4); // Printing original linked list System.out.print("Original linked list : "); printList(head1); // Step1 - Make a copy of original linked list Node newList = copyList(head1); // Step2 - Reverse a linked list Node head2 = reverseList(newList); // Printing reversed linked list System.out.print("Reversed linked list : "); printList(head2); // Step3 - Addition of a original linked list and // its reverse Node addition = addTwoLists(head1, head2); // Step4 - Reverse a addition Linked list Node result = reverseList(addition); // Step5 - Print the resultant linked list System.out.print("Resultant linked list : "); printList(result); }}// This code is contributed by sankar |
Python3
# python code of above approach# Define the structure of a# node in the linked listclass Node: def __init__(self, x): self.data = x self.next = None# Function to return the# reverse of a linked listdef reverseList(head): prev = None cur = head next_ = None while cur is not None: next_ = cur.next cur.next = prev prev = cur cur = next_ return prev# Function to return the sum of two# linked listsdef addTwoLists(l1, l2): dummy = Node(0) cur = dummy carry = 0 while l1 is not None or l2 is not None: x = l1.data if l1 else 0 y = l2.data if l2 else 0 summ = carry + x + y carry = summ // 10 cur.next = Node(summ % 10) cur = cur.next if l1: l1 = l1.next if l2: l2 = l2.next if carry > 0: cur.next = Node(carry) return dummy.next# Function to print a linked listdef printList(head): while head is not None: print(head.data, end=" ") head = head.next print()# Function to create a copy of# a linked listdef copyList(head): cur = head dummy = Node(0) copy = dummy while cur is not None: copy.next = Node(cur.data) copy = copy.next cur = cur.next return dummy.next# Driver Codeif __name__ == '__main__': # Example linked list: # 1 -> 2 -> 3 -> 4 head1 = Node(1) head1.next = Node(2) head1.next.next = Node(3) head1.next.next.next = Node(4) # Printing original linked list print("Original linked list : ", end="") printList(head1) # Step1 - Make a copy of original # linked list newList = copyList(head1) # Step2 - Reverse a linked list head2 = reverseList(newList) # Printing reversed linked list print("Reversed linked list : ", end="") printList(head2) # Step3 - Addition of a original # linked list and its reverse addition = addTwoLists(head1, head2) # Step4 - Reverse a addition # Linked list result = reverseList(addition) # Step5 - Print the resultant # linked list print("Resultant linked list : ", end="") printList(result) |
C#
// C# code implementation for the above approachusing System;// Define the structure of a node in the linked listpublic class Node { public int data; public Node next; public Node(int x) { data = x; next = null; }}public class GFG { // Function to return the reverse of a linked list static Node reverseList(Node head) { Node prev = null; Node cur = head; Node next_; while (cur != null) { next_ = cur.next; cur.next = prev; prev = cur; cur = next_; } return prev; } // Function to return the sum of two linked lists static Node addTwoLists(Node l1, Node l2) { Node dummy = new Node(0); Node cur = dummy; int carry = 0; while (l1 != null || l2 != null) { int x = l1 != null ? l1.data : 0; int y = l2 != null ? l2.data : 0; int sum = carry + x + y; carry = sum / 10; cur.next = new Node(sum % 10); cur = cur.next; if (l1 != null) { l1 = l1.next; } if (l2 != null) { l2 = l2.next; } } if (carry > 0) { cur.next = new Node(carry); } return dummy.next; } // Function to print a linked list static void printList(Node head) { while (head != null) { Console.Write(head.data + " "); head = head.next; } Console.WriteLine(); } // Function to create a copy of a linked list static Node copyList(Node head) { Node cur = head; Node dummy = new Node(0); Node copy = dummy; while (cur != null) { copy.next = new Node(cur.data); copy = copy.next; cur = cur.next; } return dummy.next; } static public void Main() { // Code // Example linked list: // 1 -> 2 -> 3 -> 4 Node head1 = new Node(1); head1.next = new Node(2); head1.next.next = new Node(3); head1.next.next.next = new Node(4); // Printing original linked list Console.Write("Original linked list : "); printList(head1); // Step1 - Make a copy of original linked list Node newList = copyList(head1); // Step2 - Reverse a linked list Node head2 = reverseList(newList); // Printing reversed linked list Console.Write("Reversed linked list : "); printList(head2); // Step3 - Addition of a original linked list and // its reverse Node addition = addTwoLists(head1, head2); // Step4 - Reverse a addition Linked list Node result = reverseList(addition); // Step5 - Print the resultant linked list Console.Write("Resultant linked list : "); printList(result); }}// This code is contributed by karthik. |
Javascript
// JavaScript code of above approach// Define the structure of a// node in the linked listclass Node {constructor(x) {this.data = x;this.next = null;}}// Function to return the// reverse of a linked listfunction reverseList(head) {let prev = null;let cur = head;let next_ = null;while (cur !== null) { next_ = cur.next; cur.next = prev; prev = cur; cur = next_;}return prev;}// Function to return the sum of two// linked listsfunction addTwoLists(l1, l2) {let dummy = new Node(0);let cur = dummy;let carry = 0;while (l1 !== null || l2 !== null) { let x = l1 ? l1.data : 0; let y = l2 ? l2.data : 0; let summ = carry + x + y; carry = Math.floor(summ / 10); cur.next = new Node(summ % 10); cur = cur.next; if (l1) { l1 = l1.next; } if (l2) { l2 = l2.next; }}if (carry > 0) { cur.next = new Node(carry);}return dummy.next;}// Function to print a linked listfunction printList(head) {while (head !== null) {console.log(head.data, end=" ");head = head.next;}console.log();}// Function to create a copy of// a linked listfunction copyList(head) {let cur = head;let dummy = new Node(0);let copy = dummy;while (cur !== null) { copy.next = new Node(cur.data); copy = copy.next; cur = cur.next;}return dummy.next;}// Driver Codeif (typeof require !== 'undefined' && require.main === module) { // Example linked list:// 1 -> 2 -> 3 -> 4let head1 = new Node(1);head1.next = new Node(2);head1.next.next = new Node(3);head1.next.next.next = new Node(4);// Printing original linked listconsole.log("Original linked list : ");printList(head1);// Step1 - Make a copy of original// linked listlet newList = copyList(head1);// Step2 - Reverse a linked listlet head2 = reverseList(newList);// Printing reversed linked listconsole.log("Reversed linked list : ");printList(head2);// Step3 - Addition of a original// linked list and its reverselet addition = addTwoLists(head1, head2);// Step4 - Reverse a addition// Linked listlet result = reverseList(addition);// Step5 - Print the resultant// linked listconsole.log("Resultant linked list : ");printList(result);}//This code is contributed by shivamsharma215 |
Output
Original linked list : 1 2 3 4 Reversed linked list : 4 3 2 1 Resultant linked list : 5 5 5 5
Time complexity: O(max(m, n)), where m and n are the lengths of the linked lists being added.
Auxiliary Space: O(max(m, n)), as the length of the resultant linked list can be at most one more than the length of the longer linked list. The copyList and reverseList functions have a time complexity of O(n), where n is the length of the linked list.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
