Question

Could someone help me out with the answering this? Explaining the theory would be very helpful

A NumberList is a linked list used to represent the digits of a number. For example 983 is represented as: [ Node(9), Node(8), Node (3) ] Write the pseudocode for an algorithm which performs addition on 2 NumberLists, such that: [ Node (9), Node(8), Node (3) ] + [ Node(1), Node (0), Node (4), Node (3)] = [ Node (2), Node(0), Node(2), Node (6)] Your pseudocode should use only the methods of the List ADT. Take care to deal with lists of different sizes. If you are using recursion, highlight the base cases.

Answer 1

Problem statement :

Adding two link lists which have their nodes rep
// Jdvd Piuyi dill LU duuLWU lumbers resulL UY LIeu CISL class NumberList { static Node headı, head2; static class Node { int data; Node next; Node(int d) data = d; next = null; /* Adds digits of two linked lists and return the head node of resultult list */ Node sumLists(Node list1, Node list2) Node result := null // result is head node of the result list Node previous := null Node temp := null int carry = 0, sum while listi is not null or list2 is not null //traversing end of both the lists // Sum each digits of list1 and list2 in result list.sum = carry + (list1 != null ? list1. data : ) + (list2 != null ? list2. data : 0) // carry update carry := (sum >= 10) ? 1:0 // sum update sum = sum % 10 // Create a new node with sum as data temp = new Node( sum) // if this is the listi node then set it as head of // the result list if result is null result := temp else // If this is not the listi node then connect it to the result. previous. next := temp // Set previous for next insertion previous := temp // Move list1 and list2 pointers to next nodes if listi is not null list1 = list1.next if list2 is not null list2 := list2.next if carry > 0 temp. next := new Node (carry) // return head of the result list return result

return result /* Display linked list */ void displayList (Node head) while head is not null Print head. data head := head. next main() Numberlist list = new Numberlist(); // creating listi list.head1 = new Node(9) list.head1. next = new Node(8) list.head1. next next = new Node (3) print "List1" list.displayList(head1) // creating list2 list.head2 = new Node(1) list.head2. next = new Node() list.head1. next next = new Node (4) list. head1. next next next = new Node(3) print "List2" list.displayList(head2); // add the two lists in result list Node resultList = list. addTwoLists(headı, head2) print "Result List" list.printList (resultList) 75 }
resenting two numbers.

Pseudo code :

 // Java program to add two numbers result by linked list class NumberList { static Node head1, head2; static class Node { int data; Node next; Node(int d) { data = d; next = null; } } /* Adds digits of two linked lists and return the head node of resultult list */ Node sumLists(Node list1, Node list2) { Node result := null // result is head node of the result list Node previous := null Node temp := null int carry := 0, sum while list1 is not null or list2 is not null //traversing end of both the lists // Sum each digits of list1 and list2 in result list. sum = carry + (list1 != null ? list1.data : 0) + (list2 != null ? list2.data : 0) // carry update carry := (sum >= 10) ? 1 : 0 // sum update sum := sum % 10 // Create a new node with sum as data temp := new Node(sum) // if this is the list1 node then set it as head of // the result list if result is null result := temp else // If this is not the list1 node then connect it to the resultt. previous.next := temp // Set previous for next insertion previous := temp // Move list1 and list2 pointers to next nodes if list1 is not null list1 = list1.next if list2 is not null list2 := list2.next if carry > 0 temp.next := new Node(carry) // return head of the result list return result } /* Display linked list */ void displayList(Node head) { while head is not null Print head.data head := head.next } main() { NumberList list = new NumberList(); // creating list1 list.head1 = new Node(9) list.head1.next = new Node(8) list.head1.next.next = new Node(3) print "List1" list.displayList(head1) // creating list2 list.head2 = new Node(1) list.head2.next = new Node(0) list.head1.next.next = new Node(4) list.head1.next.next.next = new Node(3) print "List2" list.displayList(head2); // add the two lists in result list Node resultList = list.addTwoLists(head1, head2) print "Result List" list.printList(resultList) } } 

Explaination:

Traverse both lists and add value of each list nodes. If the sum is more than 10 then carry over 1 and reduce sum. If one list has more elements than the other then take remaining values of this list as 0.