# Untitled

a guest
Feb 14th, 2020
1,265
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /**
2. * Returns the sum of two polynomials - DOES NOT change either of the input polynomials.
3. * The returned polynomial MUST have all new nodes. In other words, none of the nodes
4. * of the input polynomials can be in the result.
5. *
6. * @param poly1 First input polynomial (front of polynomial linked list)
7. * @param poly2 Second input polynomial (front of polynomial linked list
8. * @return A new polynomial which is the sum of the input polynomials - the returned node
9. * is the front of the result polynomial
10. */
11. public static Node add(Node poly1, Node poly2) {
12. if (poly1 == null && poly2 == null) return null;
13. if (poly1 == null) return poly2;
14. if (poly2 == null) return poly1;
15. Node front = new Node(0, 0, null);
16. Node ptr = front;
17. while (poly1 != null && poly2 != null) {
18. if (poly1.term.degree == poly2.term.degree) {
19. ptr.term.degree = poly1.term.degree;
20. ptr.term.coeff = poly1.term.coeff + poly2.term.coeff;
21. poly1 = poly1.next;
22. poly2 = poly2.next;
23. } else if (poly1.term.degree < poly2.term.degree) {
24. ptr.term.degree = poly1.term.degree;
25. ptr.term.coeff = poly1.term.coeff;
26. poly1 = poly1.next;
27. } else if (poly1.term.degree > poly2.term.degree) {
28. ptr.term.degree = poly2.term.degree;
29. ptr.term.coeff = poly2.term.coeff;
30. poly2 = poly2.next;
31. }
32. ptr.next = new Node(0, 0, null);
33. ptr = ptr.next;
34. }
35.
36. Node ptr2 = null;
37. if (poly1 != null) ptr2 = poly1;
38. if (poly2 != null) ptr2 = poly2;
39. while (ptr2 != null) {
40. ptr.term.degree = ptr2.term.degree;
41. ptr.term.coeff = ptr2.term.coeff;
42. if (ptr2.next != null) {
43. ptr.next = new Node(0, 0, null);
44. ptr = ptr.next;
45. }
46. ptr2 = ptr2.next;
47. }
48. simplify(front);
49. return front;
50. }
51.
52. private static void simplify(Node first) {
53. Node ptr1 = first;
54. Node ptr2;
55. Node tmp;
56.
57. while (ptr1 != null && ptr1.next != null) {
58. ptr2 = ptr1;
59.
60. while (ptr2.next != null) {
61. if (ptr1.term.degree == ptr2.next.term.degree) {
62. ptr1.term.coeff = ptr1.term.coeff + ptr2.next.term.coeff;
63. tmp = ptr2.next;
64. ptr2.next = ptr2.next.next;
65. } else {
66. ptr2 = ptr2.next;
67. }
68. }
69. ptr1 = ptr1.next;
70. }
71. }
RAW Paste Data